I'm faced with the problem of maintaining the strong components of a directed graph under insertions/deletions of edges and vertices.

As noted in one of the answers to a closely-related question here, the literature in this area is rather fragmented and hard for a newcomer such as myself to approach.

For example, the paper by Holm et al. appears to focus on undirected graphs, and it's unclear to me whether any of their results can be adapted to work with digraphs. Other papers I've found focus on either the incremental or decremental cases, rather than the fully-dynamic case.

My need arises in a real-world software engineering scenario, so I would actually be fine with an approach that yields no worst-case asymptotic advantage over the naive idea of running an SCC algorithm from scratch for each update, so long as it performs well in practice.

I'd prefer not to reinvent the wheel, but I also don't have endless hours to wade through the literature, so hopefully someone here can save me some time.

Thanks in advance!


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.