| Pebble game algorithms and (k, l)-sparse graphs. Accepted to EuroComb ’05 (2005) | |||||||||||||||||
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. | |||||||||||||||||
Publication details | |||||||||||||||||
| |||||||||||||||||