Jump to content

Path-based strong component algorithm

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by LOL (talk | contribs) at 06:09, 5 December 2008 (→References: Space after "pp.", en dash.). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.

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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Path-based_strong_component_algorithm&oldid=255993845"