Существует ли онлайн-алгоритм для отслеживания компонентов в изменяющемся неориентированном графе?

12

проблема

У меня есть неориентированный граф (с несколькими ребрами), который будет меняться со временем, узлы и ребра могут быть вставлены и удалены. При каждой модификации графика я должен обновлять связанные компоненты этого графика.

свойства

Дополнительные свойства состоят в том, что никакие два компонента никогда не будут повторно соединены. Очевидно, что граф может иметь циклы в произвольном количестве (в противном случае решение будет тривиальным). Если ребро не содержит узел n , он никогда не примет этот узел. Однако, если n e , он может измениться на n e .ennene

подходы

Пока у меня есть два возможных подхода, но, как вы увидите, они ужасны:

Медленное состояние без

Я могу искать (dfs / bfs) график, начиная с измененного элемента (ов) каждый раз. Это сохраняет пространство, но медленно, так как у нас есть O (n + m) для каждой модификации.

Быстрый (-er) (?) Подход с учетом состояния

Я могу сохранить все возможные пути для каждого узла для всех возможных узлов, но если я правильно его увижу, это займет O (n ^ 4) памяти. Но я не уверен, как улучшается среда выполнения (если она вообще есть, потому что я должен постоянно обновлять информацию для каждого узла в одном и том же компоненте).

Вопрос

Есть ли у вас какие-либо указания, как я могу узнать больше об этой проблеме или, возможно, некоторые алгоритмы, которые я могу построить?

Заметка

Если бы было значительное улучшение времени выполнения / памяти, я мог бы жить с неоптимальным решением, которое иногда говорит, что два компонента - это одно, но, конечно, я бы предпочел оптимальное решение.

битовая
источник
Если я прочитал последние два предложения в «Свойствах» правильно, то, похоже, вас интересует только проблема декремента. Если это так, не забудьте проверить работу Thorup по декрементной динамической связности. (Вы можете найти цитату через указатели Джеффа, которые предназначены для полностью динамической версии проблемы.)
Maverick Woo
@ Maverick Woo: всегда могут быть новые ребра / узлы. Я думаю, что последнее свойство не очень сильное, именно по этой причине. Это все еще квалифицируется как декремент?
битовая
Ой, я не знаю, как я пропустил самое первое предложение ... Смотрите "ответ" ниже.
Маверик Ву

Ответы:

17

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

Jeffε
источник
Это звучит круто, как только я закончу документы, я, скорее всего, приму это.
битовая
6

Я думаю, что вы ищете то, что называется алгоритмом динамического графа для декомпозиции связных компонентов. Алгоритм Хольма, де Лихтенберга и Торупа [HLT01] амортизирует полилогарифмическое время при каждом обновлении ребра. Прошло много времени с тех пор, как я смотрел на проблему в прошлый раз, поэтому, вероятно, есть более недавний прогресс.

[HLT01] Джейкоб Холм, Кристиан де Лихтенберг и Миккель Торуп. Полилогарифмические детерминированные полностью динамические алгоритмы для связности, минимального связующего дерева, 2-ребра и двусвязности. Журнал ACM , 48 (4): 723–760, июль 2001 г. http://doi.acm.org/10.1145/502090.502095

Цуёси Ито
источник
Сглазить. Ты должен мне колу.
Джефф
@JeffE: я не знал об этой игре . Но по правилам я не проиграл (я просто в состоянии «сглазил»), поэтому я не должен вам колы, пока я не скажу дальше… о, подождите минутку.
Цуёси Ито
если бы вы только могли торговать очками репутации :)
Суреш Венкат
5

(А пока позвольте мне остановиться на запросах о подключении, которых, к сожалению, может не хватить для вашего приложения.)

Многие из предыдущих работ, посвященных проблеме динамического соединения, были посвящены модели обновления ребер: вы предполагаете, что количество вершин фиксировано, и вы можете вставлять и / или удалять ребра при выполнении запросов. Если вы можете только вставить (удалить), это инкрементно (декрементно). Если вы можете сделать оба, это полностью динамично. Работа Торупа, на которую указал Джефф (и я в комментарии), все для крайних обновлений.

AFAIK, сообщество теории CS только начинает изучать обновления вершин для общих графов. Чан, Пэтрашку и Родитти провели в FOCS 2008 новаторскую работу по этому вопросу. См. Эту ссылку для самой последней (сентябрь 2010 г.) ревизии и ссылки внутри.

Маверик Ву
источник
Почему вы считаете, что Holm et. и др. подход не работает для моей проблемы? Я собирался принять это.
битовая
1
Если ваш граф имеет ограниченную степень, то теоретически вы можете эмулировать обновление вершины, используя кучу обновлений ребер. В противном случае одно обновление вершины (скажем, удаление центра звездного графа) может резко изменить связность графа, и в этом случае вам понадобится результат Chan et al.
Маверик Ву
Понимаю. В исходном вопросе я должен был сказать, что удаление вершин встречается редко, поэтому я могу позволить себе сделать это по граням.
битовая