4501
правка
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
Строка 67: | Строка 67: | ||
== Открытые вопросы == | == Открытые вопросы == | ||
Если имеется метрика, порожденная графом, то некоторым практическим приложениям ( | Если имеется метрика, порожденная графом, то некоторым практическим приложениям (например, при решении определенного класса линейных систем) требуется не просто древесная метрика, а древесная метрика, порожденная остовным деревом графа. Элкин, Эмек, Спилмен и Тенг [7] предложили алгоритм поиска остовного дерева со средней невязкой <math>O(log^2 \; n \; log \; log \; n)</math>. Остается открытым вопрос, является ли эта граница точной. | ||
== См. также == | == См. также == |
правка