Аппроксимация метрических пространств древесными метриками: различия между версиями

Перейти к навигации Перейти к поиску
м
Строка 67: Строка 67:


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


== См. также ==
== См. также ==
4501

правка

Навигация