В теории графов , А частичное к -tree представляет собой тип графа, определяется либо как подграф в K -tree или в виде графа с древесной шириной в большинстве к . Многие NP-трудные комбинаторные задачи на графах разрешимы за полиномиальное время при ограничении частичными k -деревьями при ограниченных значениях k .
График миноры [ править ]
Для любой фиксированной константы k частичные k -деревья замкнуты относительно действия миноров графа , и поэтому по теореме Робертсона – Сеймура это семейство можно охарактеризовать в терминах конечного набора запрещенных миноров . Частичные 1-деревья - это в точности леса , а их единственный запрещенный минор - треугольник. Для частичных 2-деревьев единственный запрещенный минор - это полный граф с четырьмя вершинами. Однако количество запрещенных миноров увеличивается с увеличением k . Для частичных 3-деревьев существует четыре запрещенных минора: полный граф на пяти вершинах, граф октаэдрас шестью вершинами, восьмивершинным графом Вагнера и пятиугольной призмой с десятью вершинами. [1]
Динамическое программирование [ править ]
Многие алгоритмические проблемы, которые являются NP-полными для произвольных графов, могут быть эффективно решены для частичных k -деревьев с помощью динамического программирования , используя древовидную декомпозицию этих графов. [2]
Связанные семейства графиков [ править ]
Если семейство графов имеет ограниченную ширину дерева , то это подсемейство частичных k -деревьев, где k - граница ширины дерева. Семьи графов с этим свойством включают кактус графику , pseudoforests , параллельно-графики , внешнепланарные графики , графики Халин и сети аполлоновских . [1] Например, последовательно-параллельные графы являются подсемейством частичных 2-деревьев, и, что более важно, граф является частичным 2-деревом тогда и только тогда, когда каждая из его двусвязных компонент последовательно-параллельна.
В графах потока управления , возникающих при компиляции из структурированных программ также имеют ограниченную древесную ширину, что позволяет определенные задачи , такие как выделение регистров должны быть выполнены эффективны на них. [3]
Заметки [ править ]
- ^ а б Бодлендер (1998) .
- ^ Арнборг и Проскуровски (1989) ; Берн, Лоулер и Вонг (1987) ; Бодлендер (1988) .
- ^ Thorup (1998) .
Ссылки [ править ]
- Arnborg, S .; Проскуровский А. (1989), «Алгоритмы с линейным временем для NP-сложных задач, ограниченных частичными k -деревьями», Дискретная прикладная математика , 23 (1): 11–24, DOI : 10.1016 / 0166-218X (89) 90031- 0.
- Берн, МВт; Лоулер, Э.Л . ; Вонг, Л. (1987), "Линейное время вычисление оптимальных подграфов разлагаемых графов", журнал алгоритмы , 8 (2): 216-235, DOI : 10,1016 / 0196-6774 (87) 90039-3.
- Бодлендер, Ханс Л. (1988), "Динамическое программирование на графах с ограниченной шириной дерева", Proc. 15 - й Международный коллоквиум автоматного, языки и программирование , Lecture Notes в области компьютерных наук, 317 ., Springer-Verlag, стр 105-118, DOI : 10.1007 / 3-540-19488-6_110 , ISBN 978-3-540-19488-0 CS1 maint: обескураженный параметр ( ссылка ).
- Бодлендер, Ханс Л. (1998), «Частичный k- арборетум графов с ограниченной древовидной шириной», Теоретическая информатика , 209 (1-2): 1–45, DOI : 10.1016 / S0304-3975 (97) 00228-4 , ЛВП : 1874/18312 CS1 maint: обескураженный параметр ( ссылка ).
- Thorup, Миккель (1998), "Все структурированные программы имеют небольшую ширину дерева и хорошее распределение регистров", информация и вычисления , 142 (2): 159-181, DOI : 10,1006 / inco.1997.2697 CS1 maint: обескураженный параметр ( ссылка ).
