Pebble Game Algorithms and Sparse Graphs
<|reference_start|>Pebble Game Algorithms and Sparse Graphs: A multi-graph $G$ on $n$ vertices is $(k,\ell)$-sparse if every subset of $n'\leq n$ vertices spans at most $kn'- \ell$ edges. $G$ is {\em tight} if, in addition, it has exactly $kn - \ell$ edges. For integer values $k$ and $\ell \in [0, 2k)$, we characterize the $(k,\ell)$-sparse graphs via a family of simple, elegant and efficient algorithms called the $(k,\ell)$-pebble games.<|reference_end|>
@article{lee2007pebble,
    title={Pebble Game Algorithms and Sparse Graphs},
    author={Audrey Lee and Ileana Streinu},
    journal={arXiv preprint arXiv:math/0702129},
    year={2007},
    number={UMass Amherst Computer Science Department TR 07-02},
    archivePrefix={arXiv},
    eprint={math/0702129},
    primaryClass={math.CO cs.CG}
}