4551
правка
Древесная ширина графа: различия между версиями
Перейти к навигации
Перейти к поиску
м
→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 75: | Строка 75: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Существуют алгоритмы нахождения древесной ширины с полиномиальным временем выполнения, гарантирующие нахождение ширины O(k log k) для графов с древесной шириной k, однако остается открытым вопрос, существует ли алгоритм аппроксимации для нахождения древесной ширины за полиномиальное время с постоянным качественным коэффициентом. Еще один давний вопрос заключается в том, существует ли алгоритм вычисления древесной ширины с полиномиальным временем выполнения для планарных графов. | Существуют алгоритмы нахождения древесной ширины с полиномиальным временем выполнения, гарантирующие нахождение ширины <math>O(k \sqrt{log \; k})</math> для графов с древесной шириной k, однако остается открытым вопрос, существует ли алгоритм аппроксимации для нахождения древесной ширины за полиномиальное время с постоянным качественным коэффициентом. Еще один давний вопрос заключается в том, существует ли алгоритм вычисления древесной ширины с полиномиальным временем выполнения для планарных графов. | ||
| Строка 82: | Строка 82: | ||
Основание степени для экспоненциального времени выполнения алгоритма из теоремы 3, вероятно, может быть улучшено. | Основание степени для экспоненциального времени выполнения алгоритма из теоремы 3, вероятно, может быть улучшено. | ||
== Экспериментальные результаты == | == Экспериментальные результаты == | ||