Частичное k-дерево

Частичное k-дерево — это вид графа, либо подграф k-дерева, либо граф с древесной шириной, не превосходящей k. Много комбинаторных NP-трудных задач на графах решаются за полиномиальное время, если ограничиться частичными k-деревьями c некоторым ограниченным значением k.

Миноры графов

Запрещённые миноры для частичных 3-деревьев

Для любой фиксированной константы k частичные k деревья замкнуты относительно операции взятия миноров графов, а потому по теореме Робертсона – Сеймура, такое семейство графов может быть описано конечным набором запрещённых миноров. Частичные 1-деревья — это в точности леса и их единственным запрещённым минором является треугольник. Для частичных 2-деревьев единственным запрещённым минором является полный граф с четырьмя вершинами. Однако при возрастании значения k далее число запрещённых миноров растёт. Для частичных 3-деревьев имеется четыре запрещённых минора — полный граф с пятью вершинами, октаэдральный граф с шестью вершинами, Граф Вагнера с восемью вершинами и граф пятигольной призмы с десятью вершинами[1].

Динамическое программирование

Много алгоритмических задач, NP-полных для произвольных графов, могут быть эффективно решены для частичных k-деревьев с помощью динамического программирования, если использовать древесную декомпозицию этих графов[2][3][4].

Связанные семейства графов

Если семейство графов имеет древесную ширину, ограниченную числом k, то оно является подсемейством частичных k-деревьев. Семейства графов с этим свойством включают кактусы, псевдолеса, параллельно-последовательные графы, внешнепланарные графы, графы Халина и графы Аполлония[1]. Например, параллельно-последовательные графы являются подсемейством частичных 2-деревьев. Более строго, граф является частичным 2-деревом тогда и только тогда, когда любой его шарнир является параллельно-последовательным.

Графы потока управления, возникающие при трансляции структурированных программ также имеют ограниченную древесную ширину, что позволяет некоторые задачи, такие как распределение регистров, выполнять эффективно[5].

Примечания

Литература

  • S. Arnborg, A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees // Discrete Applied Mathematics. — 1989. Т. 23, вып. 1. С. 11–24. doi:10.1016/0166-218X(89)90031-0.
  • M. W. Bern, E. L. Lawler, A. L. Wong. Linear-time computation of optimal subgraphs of decomposable graphs // Journal of Algorithms. — 1987. Т. 8, вып. 2. С. 216–235. doi:10.1016/0196-6774(87)90039-3..
  • Hans L. Bodlaender. Proc. 15th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 1988. — Т. 317. — С. 105–118. — (Lecture Notes in Computer Science). doi:10.1007/3-540-19488-6_110.
  • Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. Т. 209, вып. 1–2. С. 1–45. doi:10.1016/S0304-3975(97)00228-4..
  • Mikkel Thorup. All structured programs have small tree width and good register allocation // Information and Computation. — 1998. Т. 142, вып. 2. С. 159–181. doi:10.1006/inco.1997.2697..
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.