CODEWITHSUNDEEP
algorithmdata-structuresgraph-algorithm
Alex
Alex

Reputation: 1103

Determine remaining subgraphs after removal of a node joining them

So I ran into this problem while attempting to implement a feature:

Suppose I have a random, undirected graph of nodes, some of which are connected to each other.

Let's call every group of nodes that are reachable from each other to each other along some path a set.

Now, let's assume the graph contains only one such set (i.e., every node is reachable from every other node).

If I take a random node A and remove it from the set, I need to quickly and efficiently determine which sets remain. If A is a cut-point in the set, then removing it should split the set into two or more smaller sets. I simply need an efficient way of doing two things:

I need to be able to perform both operations moderately quickly. In essence, I'm looking for a O(log(n)) or a O(1) solution. An O(n) solution is not acceptable, since this graph may be large. I'm not particularly concerned with memory overhead. Can anyone point me in the right direction with which data structure/algorithm to use here? I've thought about things like Union-Find and Djikstra already, but they don't suit my needs. I don't want to run a full connectivity check on the entire graph every time a node is added or removed.

Upvotes: 0

Views: 362

Answers (1)

pkacprzak
pkacprzak

Reputation: 5617

There is a very good paper by Henzinger and King. I think that it answers your question directly.

This method has amortized O(log^3(n)) complexity per deleting an edge (deleting a vertex is equal to deleting all edges incident to it) and O(log(n) / loglog(n)) worst case complexity per query (are v and u in the same connected component).

In addition, there are presented many variants of this problem e.g. you can do it faster if only deleting is allowed.

Upvotes: 1

Related Questions