There is a classic linear algorithm to find every cut vertex (AKA articulation point) in a graph.

I have a usecase that does this computation after every time a non-articulation-point is inserted or deleted. An articulation point is never deleted (but may become non-articulation then deleted later).

Is there some incremental update version of this algorithm with better than linear time? The main ideas I've had are caching the depth and low values from this algorithm, but in most cases I end up needing to recalculate everything anyway.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.