# Pebble Game Algorithms and (k,l)-Sparse Graphs

2 Smith College - Computer Science Department
Smith College [Northampton]
Abstract : A multi-graph $G$ on n vertices is $(k,l)$-sparse if every subset of $n'≤n$ vertices spans at most $kn'-l$ edges, $0 ≤l < 2k$. $G$ is tight if, in addition, it has exactly $kn - l$ edges. We characterize $(k,l)$-sparse graphs via a family of simple, elegant and efficient algorithms called the $(k,l)$-pebble games. As applications, we use the pebble games for computing components (maximal tight subgraphs) in sparse graphs, to obtain inductive (Henneberg) constructions, and, when $l=k$, edge-disjoint tree decompositions.
Keywords :
Document type :
Conference papers
Domain :

Cited literature [18 references]

https://hal.inria.fr/hal-01184350
Contributor : Coordination Episciences Iam <>
Submitted on : Friday, August 14, 2015 - 11:36:47 AM
Last modification on : Monday, November 18, 2019 - 12:12:02 PM
Long-term archiving on: : Sunday, November 15, 2015 - 10:58:00 AM

### File

dmAE0136.pdf
Publisher files allowed on an open archive

### Identifiers

• HAL Id : hal-01184350, version 1

### Citation

Audrey Lee, Ileana Streinu. Pebble Game Algorithms and (k,l)-Sparse Graphs. 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), 2005, Berlin, Germany. pp.181-186. ⟨hal-01184350⟩

Record views