Jump to content

Path-based strong component algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Nutcracker2007 (talk | contribs) at 08:42, 22 July 2007 (creation of article). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.
(diff) ← Previous revision | Latest revision (diff) | Newer revision → (diff)

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 algorithms 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=146282183"