Pebble Game Algorithms and (k,l)-Sparse Graphs
Audrey Lee, Ileana Streinu
Abstract
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.
Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page