Gabow's algorithm

From Wikipedia, the free encyclopedia

In graph theory, the Cheriyan/Mehlhorn/Gabow algorithm is a linear-time method for finding strong components of a digraph. It was discovered in 1996 by J. Cheriyan and K. Mehlhorn and rediscovered in 1999 by H. Gabow and is a variation on Tarjan's algorithm. The algorithm uses a second stack to decide when to remove vertices in the same strong component from the main stack, instead of a vertex-indexed array of preorder numbers.

[edit] References

• Robert Sedgewick. Algorithms in C, Third Edition, Part 5 - Graph Algorithms. Addison-Wesley, 2002. ISBN 0-201-31663-3. Section 19.8, pp.205

• J. Cheriyan and K. Mehlhorn. Algorithms for dense graphs and networks on the random access computer, Algorithmica, volume 15, pp. 521-549, 1996.