Pebble Game Algorithms and Sparse Graphs

Details Pebble Game Algorithms and Sparse Graphs Pebble Game Algorithms and Sparse Graphs

2007-02-06

arxiv.org/abs/math/0702129v1

Mathematics

Combinatorics

20 pages, abstract presented at EuroComb '05

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Pebble Game Algorithms and Sparse Graphs 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 Pebble Game Algorithms and Sparse Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pebble Game Algorithms and Sparse Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-427341