patternMinor
Connected components and graph edition
Viewed 0 times
graphcomponentsconnectedandedition
Problem
There are known algorithms to find the connected components of a given graph. Those I know are easily extensible to support addition of nodes and edges to the graph and then find the resulting components more quickly than by recomputing from scratch.
What I'm looking for is an algorithm with an associated data structure which allow the efficient determination of connected components after removal of nodes and edges.
What I'm looking for is an algorithm with an associated data structure which allow the efficient determination of connected components after removal of nodes and edges.
Solution
In general, what you are looking for is known as dynamic connectivity: it comes with different flavors depending on whether vertices/edges can be added, deleted, or if both operations are allowed.
Many relevant papers are summarized in this answer on TCS.SE. If you are looking for a practical implementation, a possible starting point is [1]. Here, the authors perform experiments and provide some C++ code (these are for fully dynamic algorithms).
[1] Iyer, R., Karger, D., Rahul, H., & Thorup, M. "An experimental study of polylogarithmic, fully dynamic, connectivity algorithms." Journal of Experimental Algorithmics (JEA) 6 (2001): 4.
Many relevant papers are summarized in this answer on TCS.SE. If you are looking for a practical implementation, a possible starting point is [1]. Here, the authors perform experiments and provide some C++ code (these are for fully dynamic algorithms).
[1] Iyer, R., Karger, D., Rahul, H., & Thorup, M. "An experimental study of polylogarithmic, fully dynamic, connectivity algorithms." Journal of Experimental Algorithmics (JEA) 6 (2001): 4.
Context
StackExchange Computer Science Q#68332, answer score: 5
Revisions (0)
No revisions yet.