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
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.
Folding and Unfolding of Polygonal Linkages, with Applications to Structural Biology; Funder: National Science Foundation; Code: 0310661
Oriented Matroids and Rigidity Theory in Computational Geometry; Funder: National Science Foundation; Code: 0430990
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, 2017, Halifax NS Canada, 10.1145/3097983.3097995.