Audrey Lee ; Ileana Streinu - Pebble Game Algorithms and (k,l)-Sparse Graphs

dmtcs:3394 - Discrete Mathematics & Theoretical Computer Science, January 1, 2005, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) - https://doi.org/10.46298/dmtcs.3394
Pebble Game Algorithms and (k,l)-Sparse GraphsArticle

Authors: Audrey Lee 1; Ileana Streinu 2

  • 1 Department of Computer Science [Amherst]
  • 2 Computer Science Department

A multi-graph $G$ on n vertices is $(k,l)$-sparse if every subset of $n'≤n$ vertices spans at most $kn'-l$ edges, $0 ≤l < 2k$. $G$ is tight if, in addition, it has exactly $kn - l$ edges. We characterize $(k,l)$-sparse graphs via a family of simple, elegant and efficient algorithms called the $(k,l)$-pebble games. As applications, we use the pebble games for computing components (maximal tight subgraphs) in sparse graphs, to obtain inductive (Henneberg) constructions, and, when $l=k$, edge-disjoint tree decompositions.


Volume: DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: sparse graph,pebble game,rigidity,arboricity,graph orientation with bounded degree,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM],[MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO]
Funding:
    Source : OpenAIRE Graph
  • Oriented Matroids and Rigidity Theory in Computational Geometry; Funder: National Science Foundation; Code: 0430990
  • Folding and Unfolding of Polygonal Linkages, with Applications to Structural Biology; Funder: National Science Foundation; Code: 0310661

6 Documents citing this article

Consultation statistics

This page has been seen 182 times.
This article's PDF has been downloaded 353 times.