Часткове k-дерево

Часткове k-дерево — це вид графа, або підграф k-дерева, або граф з деревною шириною, що не перевищує k. Багато комбінаторних NP-складних задач на графах розв'язуються за поліноміальний час, якщо обмежитися частковими k-деревами з деяким обмеженим значенням k.

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

Заборонені мінори для часткових 3-дерев

Для будь-якої фіксованої константи k часткові k дерева замкнуті щодо операції взяття мінорів графів, тому за теоремою Робертсона — Сеймура, таке сімейство графів можна описати скінченним набором заборонених мінорів. Часткові 1-дерева — це точно ліси і їх єдиним забороненим мінором є трикутник. Для часткових 2-дерев єдиним забороненим мінором є повний граф з чотирма вершинами. Однак при зростанні значення k далі кількість заборонених мінорів зростає. Для часткових 3-дерев є чотири заборонені мінори — повний граф з п'ятьма вершинами, октаедральний граф із шістьма вершинами, граф Вагнера з вісьмома вершинами і граф п'ятикутної призми з десятьма вершинами.

Динамічне програмування

Багато алгоритмічних задач, NP-повних для довільних графів, можна ефективно розв'язати для часткових k-дерев за допомогою динамічного програмування, якщо використовувати деревну декомпозицію цих графів.

Пов'язані сімейства графів

Якщо сімейство графів має деревну ширину, обмежену числом k, воно є підсімейством часткових k-дерев. Сімейства графів із цією властивістю включають кактуси, псевдоліси, паралельно-послідовні графи, зовніпланарні графи, графи Халіна та графи Аполлонія. Наприклад, паралельно-послідовні графи є підсімейством часткових 2-дерев. Строгіше, граф є частковим 2-деревом тоді й лише тоді, коли будь-який його шарнір є паралельно-послідовним.

Графи потоку керування, що виникають при трансляції структурованих програм також мають обмежену деревну ширину, що дозволяє ефективно виконувати деякі завдання, такі як розподіл регістрів.

Література

• S. Arnborg, A. Proskurowski. Linear time algorithms for NP-hard problems restricted to partial k-trees // Discrete Applied Mathematics. — 1989. — Т. 23, вип. 1 (25 травня). — С. 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 (25 травня). — С. 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 (25 травня). — С. 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 (25 травня). — С. 159–181. — DOI:10.1006/inco.1997.2697..