4551
правка
Путевая ширина графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 50: | Строка 50: | ||
Понятие путевой ширины оказалось удобным инструментом при разработке точных субэкспоненциальных алгоритмов на планарных графах и их обобщениях. Основная идея этого подхода очень проста. Пусть <math>\mathfrak{P}</math> – задача на графах, а <math>\mathfrak{G}</math> – класс графов, такой, что: | Понятие путевой ширины оказалось удобным инструментом при разработке точных субэкспоненциальных алгоритмов на планарных графах и их обобщениях. Основная идея этого подхода очень проста. Пусть <math>\mathfrak{P}</math> – задача на графах, а <math>\mathfrak{G}</math> – класс графов, такой, что: | ||
для каждого графа <math>G \in \mathfrak{G}</math> с путевой шириной, не превышающей <math>\ell \, </math>, задача <math>\mathfrak{P}</math> может быть решена за время <math>2^{c \cdot | для каждого графа <math>G \in \mathfrak{G}</math> с путевой шириной, не превышающей <math>\ell \, </math>, задача <math>\mathfrak{P}</math> может быть решена за время <math>2^{c \cdot \ell} \cdot n^{O(1)}</math>, где c является константой; | ||
для каждого графа <math>G \in \mathfrak{G}</math> с n вершинами декомпозиция G в форме ветвления (не обязательно оптимальная) с шириной не более h(n) может быть построена за полиномиальное время, причем h(n) является функцией. | для каждого графа <math>G \in \mathfrak{G}</math> с n вершинами декомпозиция G в форме ветвления (не обязательно оптимальная) с шириной не более h(n) может быть построена за полиномиальное время, причем h(n) является функцией. | ||
В таком случае для каждого графа G | В таком случае для каждого графа <math>G \in \mathfrak{G}</math> задача <math>\mathfrak{P}</math> может быть решена за время <math>2^{c \cdot h(n)} \cdot n^{O(1)}</math>. Таким образом, все сводится к вычислению констант c и функций h(n). Эти вычисления могут быть весьма сложными. В частности, как показано в [17], для каждого планарного графа G с n вершинами путевая ширина G не превышает 4:5n < 2:1214pn. Расширения этой границы для графов, допускающих вложение на поверхности рода g, приведены в [15]. | ||
Дорн [9] использует подход с матричным умножением в динамическом программировании для оценки констант c для различных задач. К примеру, в задаче нахождения максимального независимого множества c < !/2, где ! < 2:376 представляет собой матричное умножение над кольцом, из чего следует, что эта задача на планарных графах разрешима за время O(22:52pn). В задаче нахождения минимального доминирующего множества имеем c < 4, что дает время работы метода декомпозиции в форме ветвления O(23:99 n). Представляется, что алгоритмы с временем исполнения 2°^"' могут быть построены даже для некоторых «нелокальных» задач – таких как нахождение гамильтонова цикла, связного доминирующего множества и минимального дерева Штейнера, для которых нет известных алгоритмов для графов общего вида с путевой шириной I, имеющих время исполнения 20{V> ■ nO(1) [11]. В этом случае необходимы специальные свойства некоторых оптимальных декомпозиций планарных графов в форме ветвления; грубо говоря, должно иметь место следующее: каждая дуга T соответствует диску на плоскости, такому, что все дуги G, соответствующие одному компоненту T — e, находятся внутри диска, а все остальные дуги – снаружи. Некоторые субэкспоненциальные алгоритмы на планарных графах могут быть обобщены для графов, вложенных на поверхности [10] и, далее, для классов графов, замкнутых относительно операции взятия минора [8]. | Дорн [9] использует подход с матричным умножением в динамическом программировании для оценки констант c для различных задач. К примеру, в задаче нахождения максимального независимого множества c < !/2, где ! < 2:376 представляет собой матричное умножение над кольцом, из чего следует, что эта задача на планарных графах разрешима за время O(22:52pn). В задаче нахождения минимального доминирующего множества имеем c < 4, что дает время работы метода декомпозиции в форме ветвления O(23:99 n). Представляется, что алгоритмы с временем исполнения 2°^"' могут быть построены даже для некоторых «нелокальных» задач – таких как нахождение гамильтонова цикла, связного доминирующего множества и минимального дерева Штейнера, для которых нет известных алгоритмов для графов общего вида с путевой шириной I, имеющих время исполнения 20{V> ■ nO(1) [11]. В этом случае необходимы специальные свойства некоторых оптимальных декомпозиций планарных графов в форме ветвления; грубо говоря, должно иметь место следующее: каждая дуга T соответствует диску на плоскости, такому, что все дуги G, соответствующие одному компоненту T — e, находятся внутри диска, а все остальные дуги – снаружи. Некоторые субэкспоненциальные алгоритмы на планарных графах могут быть обобщены для графов, вложенных на поверхности [10] и, далее, для классов графов, замкнутых относительно операции взятия минора [8]. | ||