Pebble Game Algorithms and Sparse Graphs

Audrey Lee, Ileana Streinu

A multi-graph $G$ on $n$ vertices is $(k,\ell )$-sparse if every subset of $n^{\prime }\le n$ vertices spans at most $k{n}^{\prime }-\ell$ edges. $G$ is {\em tight} if, in addition, it has exactly $k…