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 Graphs
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
3 Documents citing this article
Source : OpenCitations
GarcĂa, A.; Tejel, J., 2009, Augmenting The Rigidity Of A Graph In R 2, Algorithmica, 59, 2, pp. 145-168, 10.1007/s00453-009-9300-9.
Gonzรกlez, Luis C; Wang, Hui; Livesay, Dennis R; Jacobs, Donald J, 2015, A Virtual Pebble Game To Ensemble Average Graph Rigidity, Algorithms For Molecular Biology, 10, 1, 10.1186/s13015-015-0039-3.
Shen, Chih-Ya; Huang, Liang-Hao; Yang, De-Nian; Shuai, Hong-Han; Lee, Wang-Chien; Chen, Ming-Syan, 2017, On Finding Socially Tenuous Groups For Online Social Networks, Proceedings Of The 23Rd ACM SIGKDD International Conference On Knowledge Discovery And Data Mining, 10.1145/3097983.3097995.