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 GraphsConference paper

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 nn vertices spans at most knl edges, 0l<2k. G is tight if, in addition, it has exactly knl 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 272 times.
This article's PDF has been downloaded 425 times.