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

Среди других интересных вариантов остовов – ''остов с сохранением расстояния'', предложенный Боллобасом и коллегами [8], и ''легковесный остов'', предложенный Авербухом и коллегами [4]. Подграф называется d-хранителем, если он сохраняет точные расстояния между каждой парой вершин, разделенных расстоянием не менее d. Легковесный остов стремится минимизировать количество дуг и полный вес дуг. Параметр «''легкость''» определяется для подграфа как отношение полного веса всех его дуг к весу минимального остовного дерева графа. Авербух и коллеги [4] показали, что для любого взвешенного графа и целого числа k > 1 существует O(k)-остов с <math>O(k \rho n^{l+\frac{1}{k}})</math> дугами и легкостью <math>O(k \rho n^{\frac{1}{k}})</math>, где <math>\rho\ </math> = log(Diameter), который можно построить за полиномиальное время.