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

Пусть в начале второго этапа (u, v’) <math>\in</math> E’ будет дугой с наименьшим весом среди всех дуг, инцидентных u, от вершин кластера с центром в x. Таким образом, должно выполняться weight(u, v’) ≤ weight(u, v). Обработка вершины u на втором этапе алгоритма гарантирует, что дуга (u, v’) добавляется в E<math>_{S}</math>. Следовательно, существует путь ΠUV = u – v’ – x – v между u и v в остове E<math>_{S}</math>, и его вес ограничен weight(Πuv) = weight(u, v’) + weight(v’, x) + weight(x, v). Поскольку (v’, x) и (v, x) были выбраны на первом этапе, должно выполняться weight(v’, x) ≤ weight(u, v’) и weight(x, v) ≤ weight(u, v). Отсюда следует, что остов (v, E<math>_{S}</math>) имеет коэффициент растяжения 3. Кроме того, обе фазы алгоритма могут быть исполнены за время O(m) с использованием элементарных структур данных и блочной сортировки.

Аддитивные остовы: описанный выше t-остов аппроксимирует попарные расстояния с мультипликативной ошибкой; его мы будем называть мультипликативным остовом. Аналогичным образом можно определить остов, аппроксимирующий попарные расстояния с аддитивной ошибкой. Такой остов называется аддитивным остовом, а соответствующая ошибка носит название избытка. Эйнгворт и коллеги [1] представили первый аддитивный остов размера O(n3/2 log n) с избытком 2. Босуана и коллеги [7] представили алгоритм построения аддитивного остова размера O(n4/3) с избытком 6. До сих пор остается открытым вопрос, существуют ли более разреженные аддитивные остовы.

(α,β)-остов: Элкин и Пелег [11] ввели понятие (α,β)-остова для невзвешенных графов, который можно рассматривать как гибрид мультипликативного и аддитивного остовов. (α,β)-остов представляет собой подграф, такой, что расстояние между любыми двумя вершинами u, v  V в этом подграфе ограничено αδ(u, v) + β, где δ(u, v) – расстояние между вершинами u и v в исходном графе. Элкин и Пелег показали, что (1+ε, β)-остов размера O(βn1+δ) для произвольно малых ε, δ > 0 может быть вычислен за счет достаточно большого значения избытка β. Недавно Торуп и Цвик [19] разработали остов с аддитивной ошибкой, сублинейной относительно аппроксимируемого расстояния.

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