4551
правка
Ширина ленты графа: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) Нет описания правки |
||
| Строка 19: | Строка 19: | ||
''' | ''' | ||
Теорема 1. Существует эффективный алгоритм, который для графа G = (V, E) устанавливает линейный порядок | Теорема 1. Существует эффективный алгоритм, который для графа <math>G = (V, E) \; </math> устанавливает линейный порядок <math>\pi : V \rightarrow \{ 1, 2, ..., n \}</math>, для которого <math>bw_{\pi } (G) \le O \Big( (log \; n)^3 \sqrt{log \; n \; log \; log \; n} \Big) \cdot D(G)</math>. В частности, имеется полилогарифмический относительно n (poly(log n)) алгоритм аппроксимации для решения задачи нахождения ширины ленты в графах общего вида.''' | ||