Geodesic
Contraction and Treewidth Lower Bounds
Journal of Graph Algorithms and Applications, Special Issue on Selected Papers from the Engineering and Applications Track of the 12th Annual European Symposium on Algorithms (ESA 2004) , Tome 10 (2006) no. 1, pp. 5-49.

Voir la notice de l'article provenant de la source Journal of Graph Algorythms and Applications website

Edge contraction is shown to be a useful mechanism to improve lower bound heuristics for treewidth. A successful lower bound for treewidth is the degeneracy: the maximum over all subgraphs of the minimum degree. The degeneracy is polynomial time computable. We introduce the notion of contraction degeneracy: the maximum over all minors of the minimum degree. We show that the contraction degeneracy problem is NP-complete, even for bipartite graphs, but for fixed k, it is polynomial time decidable if a given graph G has contraction degeneracy at least k. Heuristics for computing the contraction degeneracy are proposed and evaluated. It is shown that these can lead in practice to considerable improvements of the lower bound for treewidth, but can perform arbitrarily bad on some examples. A study is also made for the combination of contraction with Lucena's lower bound based on Maximum Cardinality Search []. Finally, heuristics for the treewidth are proposed and evaluated that combine contraction with a treewidth lower bound technique by Clautiaux et al. [].
DOI : 10.7155/jgaa.00117
Keywords: graph, treewidth, lower bound, edge contraction, experiment 
@article{JGAA_2006_10_1_a1,
     author = {Hans Bodlaender and Thomas Wolle and Arie Koster},
     title = {Contraction and {Treewidth} {Lower} {Bounds}},
     journal = {Journal of Graph Algorithms and Applications},
     pages = {5--49},
     publisher = {mathdoc},
     volume = {10},
     number = {1},
     year = {2006},
     doi = {10.7155/jgaa.00117},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00117/}
}
TY  - JOUR
AU  - Hans Bodlaender
AU  - Thomas Wolle
AU  - Arie Koster
TI  - Contraction and Treewidth Lower Bounds
JO  - Journal of Graph Algorithms and Applications
PY  - 2006
SP  - 5
EP  - 49
VL  - 10
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00117/
DO  - 10.7155/jgaa.00117
LA  - en
ID  - JGAA_2006_10_1_a1
ER  - 
%0 Journal Article
%A Hans Bodlaender
%A Thomas Wolle
%A Arie Koster
%T Contraction and Treewidth Lower Bounds
%J Journal of Graph Algorithms and Applications
%D 2006
%P 5-49
%V 10
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00117/
%R 10.7155/jgaa.00117
%G en
%F JGAA_2006_10_1_a1
Hans Bodlaender; Thomas Wolle; Arie Koster. Contraction and Treewidth Lower Bounds. Journal of Graph Algorithms and Applications, 
							Special Issue on Selected Papers from the Engineering and Applications Track of the 12th Annual European Symposium on Algorithms (ESA 2004)
					, Tome 10 (2006) no. 1, pp. 5-49. doi : 10.7155/jgaa.00117. http://geodesic.mathdoc.fr/articles/10.7155/jgaa.00117/

Cité par Sources :