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:





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.