Jump to content

Path-based strong component algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by DavidCBryant (talk | contribs) at 15:44, 23 July 2007 (→Intro: Fixed a typo.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

In graph theory, Gabow's algorithm is a linear-time method for finding strong components of a digraph. It was discovered 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.

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
Stub icon

This computer science article is a stub. You can help Wikipedia by expanding it.

Retrieved from "https://en.wikipedia.org/w/index.php?title=Path-based_strong_component_algorithm&oldid=146548350"