Geodesic
Computational aspects of treewidth for graph
Prikladnaâ diskretnaâ matematika, no. 13 (2011), pp. 85-87.

Voir la notice de l'article provenant de la source Math-Net.Ru

A brief overview of recent results on the problem of treewidth for the graph is givev; some of the lower and upper bounds for treewidth are investigated; algorithmic methods to improve these bounds are presented. 
@article{PDM_2011_13_a43,
     author = {V. V. Bykova},
     title = {Computational aspects of treewidth for graph},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {85--87},
     publisher = {mathdoc},
     number = {13},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2011_13_a43/}
}
TY  - JOUR
AU  - V. V. Bykova
TI  - Computational aspects of treewidth for graph
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2011
SP  - 85
EP  - 87
IS  - 13
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2011_13_a43/
LA  - ru
ID  - PDM_2011_13_a43
ER  - 
%0 Journal Article
%A V. V. Bykova
%T Computational aspects of treewidth for graph
%J Prikladnaâ diskretnaâ matematika
%D 2011
%P 85-87
%N 13
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2011_13_a43/
%G ru
%F PDM_2011_13_a43
V. V. Bykova. Computational aspects of treewidth for graph. Prikladnaâ diskretnaâ matematika, no. 13 (2011), pp. 85-87. http://geodesic.mathdoc.fr/item/PDM_2011_13_a43/

[1] Robertson N., Seymour P. D., “Graph minors. II. Algorithmic aspects of treewidth”, J. Algorithms, 7 (1986), 309–322 | DOI | MR | Zbl

[2] Kleinberg J., Tardos E., Algorithm Design, Addison-Wesley, Boston, 2005

[3] Arnborg S., Corneil D. G., Proskurowski A., “Complexity of finding embeddings in a $k$-tree”, SIAM J. Alg. Disc. Math., 8 (1987), 277–284 | DOI | MR | Zbl

[4] Gogate V., Dechter R., “A complete anytime algorithm for treewidth”, Proc. UAI'04. Uncertainty in Artificial Intelligence, 2004 | Zbl

[5] Bodlaender H. L., Grigoriev A., Koster A. M. C. A., “On exact algorithms for treewidth”, Proc. 14Th Annual European Symposium on Algorithms ESA, Lecture Notes in Comput. Sci., 4168, 2006, 672–683 | MR | Zbl

[6] Bodlaender H. L., Kloks T., “Efficient and constructive algorithms for the pathwidth and treewidth of graphs”, J. Algorithms, 21 (1996), 358–402 | DOI | MR | Zbl

[7] Bodlaender H. L., Rotics U., “Computing the treewidth and the minimum fill-in with the modular decomposition”, Algorithmica, 36 (2003), 375–408 | DOI | MR | Zbl

[8] Broersma H., Dahlhaus E., Kloks T., “A linear time algorithm for minimum fill-in and tree width for distance hereditary graphs”, Disc. Appl. Math., 99 (2000), 367–400 | DOI | MR | Zbl

[9] Bouchitte V., Kratsch D., Muller H., Todinca I., “On treewidth approximations”, Disc. Appl. Math., 6 (2004), 183–196 | DOI | MR

[10] Clautiaux F., Moukrim A., Negre S., Carlier J., “Heuristic and meta-heuristic methods for computing graph treewidth”, RAIRO Oper. Res., 38 (2004), 13–26 | DOI | MR | Zbl

[11] Bykova V. V., “Vychislitelnye aspekty drevovidnoi shiriny grafov”, Prikladnaya diskretnaya matematika, 2011 (to appear)