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