Geodesic
Computational aspects of treewidth for graph
Prikladnaâ diskretnaâ matematika, no. 3 (2011), pp. 65-79.

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

The paper gives a brief overview of recent results on the graph treewidth problem. We investigate some of the lower and upper bounds for treewidth, and present algorithmic methods to improve these bounds.
Keywords: graph algorithms, treewidth, partial $k$-tree. 
@article{PDM_2011_3_a4,
     author = {V. V. Bykova},
     title = {Computational aspects of treewidth for graph},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {65--79},
     publisher = {mathdoc},
     number = {3},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2011_3_a4/}
}
TY  - JOUR
AU  - V. V. Bykova
TI  - Computational aspects of treewidth for graph
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2011
SP  - 65
EP  - 79
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2011_3_a4/
LA  - ru
ID  - PDM_2011_3_a4
ER  - 
%0 Journal Article
%A V. V. Bykova
%T Computational aspects of treewidth for graph
%J Prikladnaâ diskretnaâ matematika
%D 2011
%P 65-79
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2011_3_a4/
%G ru
%F PDM_2011_3_a4
V. V. Bykova. Computational aspects of treewidth for graph. Prikladnaâ diskretnaâ matematika, no. 3 (2011), pp. 65-79. http://geodesic.mathdoc.fr/item/PDM_2011_3_a4/

[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] Bodlaender H. L., Thilikos D. M., “Treewidth for graphs with small chordality”, Disc. Appl. Math., 79 (1997), 45–61 | DOI | MR | Zbl

[4] Parra A., Scheffler P., “Characterizations and algorithmic applications of chordal graph embeddings”, Disc. Appl. Math., 79 (1997), 171–188 | DOI | MR | Zbl

[5] Emelichev V. A., Melnikov O. I., Sarvanov V. I., Tyshkevich R. I., Lektsii po teorii grafov, Nauka, M., 1990 | MR | Zbl

[6] Rose D., Tarjan R. E., Lueker G., “Algorithmic aspects of vertex elimination on graphs”, SIAM J. Comput., 5 (1976), 146–160 | DOI | MR

[7] Buneman P., “A characterization of rigid circuit graphs”, Disc. Math., 9 (1974), 205–212 | DOI | MR | Zbl

[8] Bykova V. V., Diskretnaya matematika s ispolzovaniem EVM, RIO KrasGU, Krasnoyarsk, 2006

[9] Bodlaender H. L., Some classes of graphs with bounded treewidth, Technical Report RUU-CS-76-22, Dept. Comput. Science, Univ. Utrecht, 1998

[10] Bodlaender H. L., “A partial $k$-arboretum of graphs with bounded treewidth”, Theor. Comput. Sci., 209 (1998), 1–45 | DOI | MR | Zbl

[11] Blair J. R. S., Peyton B., “An introduction to chordal graphs and clique trees”, Graph theory and sparse matrix computation, Springer, New York, 1993, 1–29 | MR | Zbl

[12] Berry A., “A wide-range efficient algorithm for minimal triangulation”, Proc. Tenth Annual ACM-SIAM Symposium on Disc. Algorithms, SIAM, Philadelphia, 1999, 860–861 | Zbl

[13] Berry A., Heggernes P., Simonet G., “The minimum degree heuristic and the minimal triangulation process”, LNCS, 2880, 2003, 58–70 | MR | Zbl

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

[15] Gogate V., Dechter R., “A complete anytime algorithm for treewidth”, Proc. 20Th Conference on Uncertainty in Artificial Intelligence, AUAI Press, Arlington, Virginia, USA, 2004, 201–208

[16] Bodlaender H. L., Fomin F. V., Koster A. M. C. A., et al., “On exact algorithms for treewidth”, LNCS, 4168, 2006, 672–683 | MR | Zbl

[17] 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

[18] 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

[19] 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

[20] Broersma H., Kloks T., Kratsch D., Muller H., “A generalization of AT-free graphs and a generic algorithm for solving triangulation problems”, Algorithmica, 32 (2002), 594–610 | DOI | MR | Zbl

[21] Bodlaender H. L., Fluiter B., “Parallel algorithms for series parallel graphs and graphs with treewidth two”, Algorithmica, 29 (2001), 543–559 | MR

[22] Amir E., “Efficient approximations for triangulation of minimum treewidth”, Proc. 17Th Conference on Uncertainty in Artificial Intelligence, Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2001, 7–15

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

[24] 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

[25] Eppstein D., “Diameter and treewidth in minor-closed families”, Algorithmica, 27 (2000), 275–291 | DOI | MR | Zbl

[26] Karpov D. V., “Razdelyayuschie mnozhestva v $k$-svyaznom grafe”, Zap. nauchn. semin. POMI, 340, 2006, 33–60 | MR | Zbl

[27] Karpov D. V., Pastor A. V., “O strukture $k$-svyaznogo grafa”, Zap. nauchn. semin. POMI, 266, 2000, 76–106 | MR | Zbl

[28] Evstigneev A. A., Kasyanov V. N., Slovar po grafam v informatike, OOO “Sibir. nauchn. izd-vo”, Novosibirsk, 2000

[29] Tursunbai kyzy Y., “Derevya klik khordalnogo grafa i derevya podgrafov”, Konstruirovanie i optimizatsiya programm, 16, Institut sistem informatiki SO RAN, Novosibirsk, 2008, 314–321

[30] Bykova V. V., Nikulskaya N. A., “Algoritmicheskie aspekty minimalnykh triangulyatsii grafa”, Trudy XIV Mezhd. konf. po event. matem. i smezhnym voprosam, KGTEI, SFU, Krasnoyarsk, 2010, 26–32

[31] Scherbina O. A., “Lokalnye eliminatsionnye algoritmy resheniya razrezhennykh diskretnykh zadach”, Zhurn. vychisl. matem. i matem. fiz., 48:1 (2008), 159–175 | MR | Zbl