ГлавнаяАрхивВычислительные аспекты древовидной ширины графа

Вычислительные аспекты древовидной ширины графа | Прикладная дискретная математика. 2011. № 3(13).

Дан краткий обзор современных результатов по проблеме вычисления древовидной ширины. Представлены и исследованы некоторые нижние и верхние оценки данного числового параметра графа. Предложены алгоритмические методы улучшения этих оценок.
  • Title Вычислительные аспекты древовидной ширины графа
  • Headline Вычислительные аспекты древовидной ширины графа
  • Publesher Tomask State UniversityTomsk State University
  • Issue Прикладная дискретная математика 3(13)
  • Date:
  • DOI
Ключевые слова
partial k-tree, treewidth, graph algorithms, древовидная ширина, частичные k-деревья, алгоритмы на графах
Авторы
Ссылки
Щербина О. А. Локальные элиминационные алгоритмы решения разреженных дискретных задач // Журн. вычисл. матем. и матем. физ. 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.
Вычислительные аспекты древовидной ширины графа | Прикладная дискретная математика. 2011. № 3(13).
Вычислительные аспекты древовидной ширины графа | Прикладная дискретная математика. 2011. № 3(13).
Полнотекстовая версия