Pebble game algorithms and sparse graphs

Author name not available (Why is that?)

Abstract: A multi-graph

G

on

n

vertices is

(k, e l l)

-sparse if every subset of

n^{'} l e q n

vertices spans at most

k n^{'} - e l l

edges.

G

is {em tight} if, in addition, it has exactly

k n - e l l

edges. For integer values

k

and

e l l i n [0, 2 k)

, we characterize the

(k, e l l)

-sparse graphs via a family of simple, elegant and efficient algorithms called the

(k, e l l)

-pebble games.

No records found.

No records found.

This page was built for publication: Pebble game algorithms and sparse graphs