4
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.