Geodesic
Pebble Game Algorithms and (k,l)-Sparse Graphs
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2005_special_250_a3,
     author = {Lee, Audrey and Streinu, Ileana},
     title = {Pebble {Game} {Algorithms} and {(k,l)-Sparse} {Graphs}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)},
     year = {2005},
     doi = {10.46298/dmtcs.3394},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3394/}
}
TY  - JOUR
AU  - Lee, Audrey
AU  - Streinu, Ileana
TI  - Pebble Game Algorithms and (k,l)-Sparse Graphs
JO  - Discrete mathematics & theoretical computer science
PY  - 2005
VL  - DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3394/
DO  - 10.46298/dmtcs.3394
LA  - en
ID  - DMTCS_2005_special_250_a3
ER  - 
%0 Journal Article
%A Lee, Audrey
%A Streinu, Ileana
%T Pebble Game Algorithms and (k,l)-Sparse Graphs
%J Discrete mathematics & theoretical computer science
%D 2005
%V DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3394/
%R 10.46298/dmtcs.3394
%G en
%F DMTCS_2005_special_250_a3
Lee, Audrey; Streinu, Ileana. Pebble Game Algorithms and (k,l)-Sparse Graphs. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05), DMTCS Proceedings vol. AE, European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05) (2005). doi : 10.46298/dmtcs.3394. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3394/

Cité par Sources :