Sparsity-certifying Graph Decompositions |
| |
Authors: | Ileana Streinu Louis Theran |
| |
Affiliation: | (1) Department of Computer Science, Smith College, Northampton, MA, USA;(2) Department of Computer Science, University of Massachusetts Amherst, Amherst, USA |
| |
Abstract: | We describe a new algorithm, the (k, ℓ)-pebble game with colors, and use it to obtain a characterization of the family of (k, ℓ)-sparse graphs and algorithmic solutions to a family of problems concerning tree decompositions of graphs. Special instances of sparse graphs appear in rigidity theory and have received increased attention in recent years. In particular, our colored pebbles generalize and strengthen the previous results of Lee and Streinu [12] and give a new proof of the Tutte-Nash-Williams characterization of arboricity. We also present a new decomposition that certifies sparsity based on the (k, ℓ)-pebble game with colors. Our work also exposes connections between pebble game algorithms and previous sparse graph algorithms by Gabow [5], Gabow and Westermann [6] and Hendrickson [9]. Ileana Streinu; Research of both authors funded by the NSF under grants NSF CCF-0430990 and NSF-DARPA CARGO CCR-0310661 to the first author. |
| |
Keywords: | Sprase graphs tree decompositions matroids |
本文献已被 SpringerLink 等数据库收录! |
|