1
$\begingroup$

I have read about papers in the last 20 years that have solved this problem. Many are mentioned in http://jamiemorgenstern.com/teaching/s18-6550/notes/notes-lec4-dgc.pdf

Unfortunately the only implementations I have found are also 20 years old and no longer compile due to changing LEDA and C++ (from the ACM DL).

Can anybody suggest any implementations that are open source, poly logarithmic time complexity, and support fully dynamic connected components? By that I mean the capability to add and remove edges without recalculating everything. Polylog seems to be the best possible so that is what I am hoping to find.

Some example papers that sounded promising:

https://u.cs.biu.ac.il/~liamr/p723-holm.pdf

https://people.csail.mit.edu/rahul/papers/dyncon-jea2001.pdf

https://www.semanticscholar.org/paper/An-Empirical-Study-of-Dynamic-Graph-Algorithms-Alberts-Cattaneo/d3efbed24e526b42da5d001036519c9b0fa79856

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.