Sparsity-certifying Graph Decompositions

Details Sparsity-certifying Graph Decompositions Sparsity-certifying Graph Decompositions

2007-03-31

arxiv.org/abs/0704.0002v2

Mathematics

Combinatorics

To appear in Graphs and Combinatorics

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Sparsity-certifying Graph Decompositions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Sparsity-certifying Graph Decompositions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Sparsity-certifying Graph Decompositions will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-552304