4551
правка
Ширина ленты графа: различия между версиями
Материал из WEGA
→Открытые вопросы
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 47: | Строка 47: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Вначале сформулируем гипотезу о ширине ленты (подробнее, например, в [13]). | Вначале сформулируем гипотезу о ширине ленты (подробнее, например, в [13]). | ||
'''Гипотеза: для любого графа G = (V, E) с n вершинами имеем <math>bw(G) = O(log \; n) \cdot D(G) \;</math>.''' | |||
Эта интересная гипотеза не доказана даже для специального случая, когда G является деревом (в [ ] приведены наилучшие результаты для деревьев). Наилучшая известная граница в общем случае, основанная на работах [7, 10], имеет вид <math>bw(G) = O(log \; n)^{3.5} \cdot D(G)</math>. Известно, что приведенная в гипотезе верхняя граница является наилучшей возможной, даже для деревьев [4]. Можно ожидать, что подобные комбинаторные исследования позволят усовершенствовать алгоритмы аппроксимации. | |||
Однако наилучшие алгоритмы аппроксимации, достигающие показателя <math>O((log \; n)^3 (log \; log \; n)^{1/4)}</math>, не основываются на границе локальной плотности. Они скорее представляют собой гибрид подходов полуопределенного программирования [1, 5] с учетом предложений Файги и методов вложения с учетом объема, изложенных в [12, 16]. Определение аппроксимируемости задачи нахождения ширины ленты графа является значимой открытой проблемой; для ее решения требуется улучшение как верхней, так и нижней границ. | |||
== Литература == | == Литература == | ||
