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
NULL##NULL
Audrey Lee;Ileana Streinu
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.
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
Bibliographic References
6 Documents citing this article
Chih-Ya Shen;Liang-Hao Huang;De-Nian Yang;Hong-Han Shuai;Wang-Chien Lee;et al., Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, On Finding Socially Tenuous Groups for Online Social Networks, pp. 415-424, 2017, Halifax NS Canada, 10.1145/3097983.3097995.