Более жесткий анализ модифицированного алгоритма Borůvka

Question

Алгоритм Борхвки является одним из стандартных алгоритмов для расчета минимального дерева охватки для графика $ g = (v, e) $, с $ | v | = n, | e | = M $.

Псевдокод:

MST T = empty tree
Begin with each vertex as a component
While number of components > 1
    For each component c
       let e = minimum edge out of component c
       if e is not in T
           add e to T  //merging the two components connected by e

Мы называем каждую итерацию внешней петли в раунде. В каждом раунде внутренняя петля сокращает количество компонентов, по крайней мере, пополам. Поэтому существует не более $ o ( log n) $ раунды. В каждом раунде внутренняя петля смотрит по каждому краю не более дважды (один раз из каждого компонента). Поэтому время выполнения больше $ O (M log n) $.

Теперь предположим, что после каждого раунда мы удаляем все края, которые подключают только вершины в одном и том же компоненте, а также удаляем дублирующиеся края между компонентами, так что внутренний цикл рассматривает только некоторое количество краев m '<m, которые являются минимальными краями веса, которые являются краями веса, которые являются ребрами, которые являются ребрами, которые являются минимальными краями, которые являются минимальными краями Подключите два ранее отключенных компонента.

Как эта оптимизация влияет на время работы?

Если бы мы как -то знали, что в каждом раунде это сократило бы количество ребра вдвое, то время работы было бы значительно улучшено: $ t (m) = t (m /2) + o (m) = O (m) $.

Однако, хотя оптимизация значительно уменьшит количество изученных краев (только 1 преимущество в последнем раунде, и больше всего # избирателей выбирают 2 в целом), неясно, как/если мы можем использовать этот факт для ужесточения анализа Время выполнения.

Answer 1

Можно создать тестовые примеры для общих графиков, где шаг вашего Borůvka не снизит количество ребра на каждом шаге, даже если он вдвое увеличивает количество вершин. Интересно, что оптимизация, которую вы предлагаете, работает для плоских графиков. Это потому, что для плоских графиков $ | e | leq 3*| v | -6 $ i, e $ | e | = O (| V |) $. И в целом это приводит к скорости для класса незначительных закрытых семей с графиками.

Ссылка:

• Тезис Мастерс, Клод Андерсон (на странице 100 наихудший ввод для алгоритма Борхвки описан). ссылка на сайт

• «Два линейных алгоритма времени для MST на незначительных классах закрытых графиков». Archivum Mathematicum 40 (3): 315–320, 2004. ссылка на сайт