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

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