diophantus

Log in | Create account
Hello, this is beta version of diophantus. If you want to report about a mistake, please, write to hello@diophantus.org

pdf Sparsity-certifying Graph Decompositions

Streinu Ileana, Theran Louis
30 Mar 2007 math.CO, cs.CG arxiv.org/abs/0704.0002
Abstract. We describe a new algorithm, the $(k,\ell)$-pebble game with colors, and use it obtain a characterization of the family of $(k,\ell)$-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 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,\ell)$-pebble game with colors. Our work also exposes connections between pebble game algorithms and previous sparse graph algorithms by Gabow, Gabow and Westermann and Hendrickson.

Reviews

There are no reviews yet.


Comments

There are no comments yet.

Log in to leave a comment.


Reviews

There are no reviews yet.

Log in to leave a review.