Часткове k-дерево
Матеріал з Вікіпедії — вільної енциклопедії.
Часткове k-дерево — це вид графа, який визначають, як підграф k-дерева або граф з деревною шириною, що не перевищує k. Багато комбінаторних NP-складних задач на графах розв'язуються за поліноміальний час, якщо обмежитися частковими k-деревами з деяким обмеженим значенням k.
Для будь-якої фіксованої константи 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: .
- 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: ..
- Hans L. Bodlaender. Proc. 15th International Colloquium on Automata, Languages and Programming. — Springer-Verlag, 1988. — Т. 317. — С. 105–118. — (Lecture Notes in Computer Science) — DOI:
- Hans L. Bodlaender. A partial k-arboretum of graphs with bounded treewidth // Theoretical Computer Science. — 1998. — Т. 209, вип. 1–2. — С. 1–45. — DOI: ..
- Mikkel Thorup. All structured programs have small tree width and good register allocation // Information and Computation. — 1998. — Т. 142, вип. 2. — С. 159–181. — DOI: ..
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.