Часткове k дерево це вид графа який визначають як підграф k дерева або граф з деревною шириною що не перевищує k Багато

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

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

Для будь-якої фіксованої константи 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. — С. 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..

[FOOTNOTEBodlaender1998-1] Bodlaender, 1998.

[FOOTNOTEArnborg,_Proskurowski1989-2] Arnborg, Proskurowski, 1989.

[FOOTNOTEBern,_Lawler,_Wong1987-3] Bern, Lawler, Wong, 1987.

[FOOTNOTEBodlaender1988-4] Bodlaender, 1988.

[FOOTNOTEThorup1998-5] Thorup, 1998.