Аноним

Путевая ширина графа: различия между версиями

Материал из WEGA

Путевая ширина графа (посмотреть исходный код)

Версия от 23:50, 12 августа 2012

76 байт убрано ,  12 августа 2012
→‎Основные результаты
Строка 48: Строка 48:
   
   


Понятие путевой ширины оказалось удобным инструментом при разработке точных субэкспоненциальных алгоритмов на планарных графах и их обобщениях. Основная идея этого подхода очень проста. Пусть <math>\mathfrak{P}</math> – задача на графах, а <math>\mathfrak{G}</math> – класс графов, такой, что:
Понятие путевой ширины оказалось удобным инструментом при разработке точных субэкспоненциальных алгоритмов на планарных графах и их обобщениях. Основная идея этого подхода очень проста. Пусть P – задача на графах, а <math>\mathcal{G}</math> – класс графов, такой, что:


для каждого графа <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 \mathcal{G}</math> с путевой шириной, не превышающей <math>\ell \, </math>, задача P может быть решена за время <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 \mathcal{G}</math> с n вершинами декомпозиция G в форме ветвления (не обязательно оптимальная) с шириной не более h(n) может быть построена за полиномиальное время, причем h(n) является функцией.


В таком случае для каждого графа <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].
В таком случае для каждого графа <math>G \in \mathcal{G}</math> задача P может быть решена за время <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].
Irina
4446

правок

Источник — http://pco.iis.nsk.su/wega/index.php/Служебная:Сравнение_версий/10319