Thepaper gives a brief overview of recent results on the graph treewidth problem. We investigatesome of the lower and upper bounds for treewidth, and present algorithmic methods toimprove these bounds.
Download file
Counter downloads: 193
- Title Computational aspects of graph treewidth
- Headline Computational aspects of graph treewidth
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(13)
- Date:
- DOI
Keywords
partial k-tree, treewidth, graph algorithms, древовидная ширина, частичные k-деревья, алгоритмы на графахAuthors
References
Щербина О. А. Локальные элиминационные алгоритмы решения разреженных дискретных задач // Журн. вычисл. матем. и матем. физ. 2008. Т. 48. №1. C. 159-175.
Быкова В. В., Никульская Н. А. Алгоритмические аспекты минимальных триангуляций графа // Труды XIV Межд. конф. по эвент. матем. и смежным вопросам. Красноярск: КГТЭИ, СФУ, 2010. C. 26-32.
Турсунбай кызы Ы. Деревья клик хордального графа и деревья подграфов // Конструирование и оптимизация программ. Новосибирск: Институт систем информатики СО РАН, 2008. Вып. 16. С. 314-321.
Евстигнеев А. А., Касьянов В. Н. Словарь по графам в информатике. Новосибирск: ООО «Сибир. научн. изд-во», 2000.
Карпов Д. В., Пастор А. В. О структуре k-связного графа // Зап. научн. семин. ПОМИ. 2000. Т. 266. С. 76-106.
Карпов Д. В. Разделяющие множества в k-связном графе // Зап. научн. семин. ПОМИ. 2006. Т. 340. С. 33-60.
Eppstein D. Diameter and treewidth in minor-closed families // Algorithmica. 2000. V. 27. P. 275-291.
Clautiaux F., Moukrim A., Negre S., and Carlier J. Heuristic and meta-heuristic methods for computing graph treewidth // RAIRO Oper. Res. 2004. V.38. P. 13-26.
Bouchitte V., Kratsch D., Muller H., and Todinca I. On treewidth approximations // Disc. Appl. Math. 2004. V. 6. P. 183-196.
Amir E. Efficient approximations for triangulation of minimum treewidth // Proc. 17Th Conference on Uncertainty in Artificial Intelligence. CA, USA: Morgan Kaufmann Publishers Inc. San Francisco, 2001. P. 7-15.
Bodlaender H. L. and Fluiter B. Parallel algorithms for series parallel graphs and graphs with treewidth two // Algorithmica. 2001. V.29. P. 543-559.
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.
Broersma H., Kloks T., Kratsch D., and Muller H. A generalization of AT-free graphs and a generic algorithm for solving triangulation problems // Algorithmica. 2002. V. 32. P. 594-610.
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.
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., Fomin F. V., Koster A. M. C. A, et al. On exact algorithms for treewidth // LNCS. 2006. V. 4168. P. 672-683.
Gogate V. and Dechter R. A complete anytime algorithm for treewidth // Proc. 20Th Conference on Uncertainty in Artificial Intelligence. Arlington, Virginia, USA: AUAI Press, 2004. P. 201-208.
Arnborg S., Corneil D. G., and Proskurowski A. Complexity of finding embeddings in a ktree// SIAM J. Alg. Disc. Meth. 1987. V.8. P. 277-284.
Berry A., Heggernes P., and Simonet G. The minimum degree heuristic and the minimal triangulation process // LNCS. 2003.V.2880. P. 58-70.
Berry A. A wide-range efficient algorithm for minimal triangulation // Proc. Tenth Annual ACM-SIAM Symposium on Disc. Algorithms. Philadelphia: SIAM, 1999. P. 860-861.
Blair J. R. S. and Peyton B. An introduction to chordal graphs and clique trees // Graph theory and sparse matrix computation. New York: Springer, 1993. P. 1-29.
Bodlaender H. L. A partial k-arboretum of graphs with bounded treewidth // Theor. Comput. Sci. 1998. V. 209. P. 1-45.
Bodlaender H. L. Some classes of graphs with bounded treewidth // Technical Report RUUCS- 76-22, Dept. Comput. Science, Univ. Utrecht, 1998.
Быкова В. В. Дискретная математика с использованием ЭВМ. Красноярск: РИО Крас- ГУ, 2006.
Buneman P. A characterization of rigid circuit graphs // Disc. Math. 1974. V. 9. P. 205-212.
Rose D., Tarjan R. E., and Lueker G. Algorithmic aspects of vertex elimination on graphs // SIAM J. Comput. 1976. V. 5. P. 146-160.
Емеличев В. А, Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990.
Parra A. and Scheffler P. Characterizations and algorithmic applications of chordal graph embeddings // Disc. Appl. Math. 1997. V. 79. P. 171-188.
Bodlaender H. L. and Thilikos D. M. Treewidth for graphs with small chordality // Disc. Appl. Math. 1997. V. 79. P. 45-61.
Kleinberg J. and Tardos E. Algorithm Design. Boston: Addison-Wesley, 2005.
Robertson N. and Seymour P. D. Graph minors. II. Algorithmic aspects of treewidth // J. Algorithms. 1986. V. 7. P. 309-322.
Computational aspects of graph treewidth | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2011. № 3(13).
Download full-text version
Download fileCounter downloads: 252