Кинетическое минимальное остовное дерево

Кинетическое минимальное связующее дерево — это кинетическая структура данных , которая поддерживает минимальное связующее дерево (MST) графа, веса ребер которого изменяются как непрерывная функция времени.

Общий случай

Наиболее эффективная известная структура данных для общего случая использует кинетически отсортированный список для хранения весов ребер и стандартный алгоритм MST для вычисления MST с учетом отсортированных весов ребер. Эта структура данных должна обрабатывать $O(n^{2})$ событий, разработка более эффективной структуры данных остается открытой проблемой.

Графы без H-миноров

Агарвал и др. разработал структуру данных, которая поддерживает MST для графа, принадлежащего второстепенному закрытому семейству . Он использует идею «обмена», вычисляя величину, на которую увеличится вес MST, если какое-то ребро в дереве e будет заменено ребром f вне дерева, так что круг, индуцированный f в дереве, содержит e . В таком случае обслуживание дерева эквивалентно поиску и замене следующей пары, для которой эта величина становится отрицательной. Эта структура данных учитывает двойное представление графа, а затем разделяется на основе ограниченных разделов Фредериксона. чтобы сделать это эффективным. Это приводит к общему времени работы $O(pn^{\frac {1}{2}}\log ^{\frac {3}{2}}n)$ если $p$ производятся вставки или удаления, или $O(n^{\frac {19}{12}}\log ^{\frac {3}{2}}n)$ если разрешены только изменения веса. Эти детерминированные границы немного улучшаются, если допускается рандомизация.

Дальнейшее чтение

• Агарвал, Панкадж; Эппштейн, Дэвид; Гибас, Леонидас Дж.; Хензингер, Моника Р. (1998). Параметрические и кинетические минимальные остовные деревья (PDF) . ФОКС . Проверено 19 мая 2012 г.