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

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

В дополнение к вышеупомянутым исследованиям по остовам общего вида было проведена большая работа по вычислению остовов для специальных классов графов – к примеру, хордальных графов, невзвешенных графов и евклидовых графов. Для хордальных графов Пелег и Шеффер [14] разработали алгоритм, вычисляющий 2-остов размера O(n3/2) и 3-остов размера O(nlogn). Для невзвешенных графов Халперин и Цвик [13] создали алгоритм с временем исполнения O(m). Салоу [17] представил алгоритм для вычисления (1+ε)-остова d-мерного полного евклидова графа за время <math>O(n log n + \frac{n}{εd})</math>. Однако ни один из алгоритмов для таких специальных случаев не подходит для работы с взвешенными неориентированными графами общего вида.