Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4650601 | Discrete Mathematics | 2008 | 13 Pages |
Abstract
A multi-graph G on n vertices is (k,ℓ)(k,ℓ)-sparse if every subset of n′⩽nn′⩽n vertices spans at most kn′-ℓkn′-ℓ edges. G is tight if, in addition, it has exactly kn-ℓkn-ℓ edges. For integer values k and ℓ∈[0,2k)ℓ∈[0,2k), we characterize the (k,ℓ)(k,ℓ)-sparse graphs via a family of simple, elegant and efficient algorithms called the (k,ℓ)(k,ℓ)-pebble games.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Audrey Lee, Ileana Streinu,