4551
правка
Путевая ширина графа: различия между версиями
Перейти к навигации
Перейти к поиску
→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 48: | Строка 48: | ||
Понятие путевой ширины оказалось удобным инструментом при разработке точных субэкспоненциальных алгоритмов на планарных графах и их обобщениях. Основная идея этого подхода очень проста. Пусть P – задача на графах, а G – класс графов, такой, что: | Понятие путевой ширины оказалось удобным инструментом при разработке точных субэкспоненциальных алгоритмов на планарных графах и их обобщениях. Основная идея этого подхода очень проста. Пусть <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 h(n)} \cdot n^{O(1)}</math>, где c является константой; | |||
для каждого графа <math>G \in \mathfrak{G}</math> с n вершинами декомпозиция G в форме ветвления (не обязательно оптимальная) с шириной не более h(n) может быть построена за полиномиальное время, причем h(n) является функцией. | |||
В таком случае для каждого графа G 2 G задача P может быть решена за время 2c'h(-rC> ■ nO(1). Таким образом, все сводится к вычислению констант c и функций h(n). Эти вычисления могут быть весьма сложными. В частности, как показано в [17], для каждого планарного графа G с n вершинами путевая ширина G не превышает 4:5n < 2:1214pn. Расширения этой границы для графов, допускающих вложение на поверхности рода g, приведены в [15]. | В таком случае для каждого графа G 2 G задача P может быть решена за время 2c'h(-rC> ■ nO(1). Таким образом, все сводится к вычислению констант c и функций h(n). Эти вычисления могут быть весьма сложными. В частности, как показано в [17], для каждого планарного графа G с n вершинами путевая ширина G не превышает 4:5n < 2:1214pn. Расширения этой границы для графов, допускающих вложение на поверхности рода g, приведены в [15]. | ||