Sparsity-certifying Graph Decompositions

Ileana Streinu, Louis Theran

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 f…