Частичное k-дерево - Википедия - Partial k-tree

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

График миноров

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

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

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

Многие алгоритмические проблемы, которые НП-полный для произвольных графов может быть эффективно решена для частичных k-деревья динамическое программирование, с использованием разложение дерева этих графиков.[2]

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

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

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

Примечания

  1. ^ а б Бодлендер (1998).
  2. ^ Арнборг и Проскуровский (1989); Берн, Лоулер и Вонг (1987); Бодлендер (1988).
  3. ^ Thorup (1998).

Рекомендации

  • Arnborg, S .; Проскуровский А. (1989), "Линейные временные алгоритмы для NP-трудных задач, ограниченных частичными k-деревья ", Дискретная прикладная математика, 23 (1): 11–24, Дои:10.1016 / 0166-218X (89) 90031-0.
  • Bern, M. W .; Лоулер, Э.; Вонг, А. Л. (1987), "Вычисление за линейное время оптимальных подграфов разложимых графов", Журнал алгоритмов, 8 (2): 216–235, Дои:10.1016/0196-6774(87)90039-3.
  • Бодландер, Ханс Л. (1988), «Динамическое программирование на графах с ограниченной шириной дерева», Proc. 15-й Международный коллоквиум по автоматам, языкам и программированию, Конспект лекций по информатике, 317, Springer-Verlag, стр. 105–118, Дои:10.1007/3-540-19488-6_110, ISBN  978-3-540-19488-0.
  • Бодландер, Ханс Л. (1998), "Частичный k-арборетум графов с ограниченной шириной дерева », Теоретическая информатика, 209 (1–2): 1–45, Дои:10.1016 / S0304-3975 (97) 00228-4, HDL:1874/18312.
  • Торуп, Миккель (1998), «Все структурированные программы имеют небольшую ширину дерева и хорошее размещение регистров», Информация и вычисления, 142 (2): 159–181, Дои:10.1006 / inco.1997.2697.