Computational aspects of treewidth for graph
Download file
Counter downloads: 270
Keywords
Authors
| Name | Organization | |
| Bykova V. V. | Siberian Federal University, Krasnoyarsk | bykvalen@mail.ru |
References
Robertson N. and Seymour P. D. Graph minors. II. Algorithmic aspects of treewidth // J. Algorithms. 1986. V. 7. P. 309-322.
Kleinberg J. and Tardos E. Algorithm Design. Boston: Addison-Wesley, 2005.
Arnborg S., Corneil D. G., and Proskurowski A. Complexity of finding embeddings in a ktree // SIAM J. Alg. Disc. Math. 1987. V.8. P. 277-284.
Gogate V. and Dechter R. A complete anytime algorithm for treewidth // Proc. UAI'04. Uncertainty in Artificial Intelligence. 2004.
Bodlaender H. L., Grigoriev A, and Koster A. M. C. A. On exact algorithms for treewidth // Proc. 14Th Annual European Symposium on Algorithms ESA. 2006. V. 4168. P. 672-683.
Bodlaender H. L. and Kloks T. Efficient and constructive algorithms for the pathwidth and treewidth of graphs // J. Algorithms. 1996. V.21. P. 358-402.
Bodlaender H. L. and Rotics U. Computing the treewidth and the minimum fill-in with the modular decomposition // Algorithmica. 2003. V. 36. P. 375-408.
Broersma H., Dahlhaus E., and Kloks T. A linear time algorithm for minimum fill-in and tree width for distance hereditary graphs // Disc. Appl. Math. 2000. V. 99. P. 367-400.
Bouchitte V., Kratsch D., MullerH., and Todinca I. On treewidth approximations // Disc. Appl. Math. 2004. V. 6. P. 183-196.
Clautiaux F., Moukrim A., NegreS., and Carlier J. Heuristic and meta-heuristic methods for computing graph treewidth // RAIRO Oper. Res. 2004. V.38. P. 13-26.
Быкова В. В. Вычислительные аспекты древовидной ширины графов // Прикладная дискретная математика. 2011 (в печати).
