Path-based strong component algorithm
In graph theory, the Cheriyan–Mehlhorn/Gabow algorithm is a linear-time method for finding the strong components of a digraph. It was discovered in 1996 by Joseph Cheriyan and Kurt Mehlhorn [1] and rediscovered in 1999 by Harold N. Gabow [2] 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.
The algorithm is easily derived from the "path-based view" of depth-first search. This contrasts with the more widely known "tree-based view" [3]. The path-based view conceptualizes a depth-first search as constructing a sequence of paths [4]. The tree-based view conceptualizes the search as constructing a depth-first spanning tree. The path-based view is simpler and can be used to derive most basic depth-first search algorithms (e.g., topological ordering, strong and biconnected components) [5]. The tree-based view is more powerful and provides the framework for more advanced graph algorithms (e.g., planarity testing, triconnected components).
References
- ^ Cheriyan, J.; [[Kurt Mehlhorn
title=Algorithms for dense graphs and networks on the random access computer|Mehlhorn, K.]] (1996). Algorithmica. 15: 521–549.
{{cite journal}}: Missing or empty|title=(help); Missing pipe in:|author2-link=(help); line feed character in|author2-link=at position 14 (help) - ^ Sedgewick, R. (2002). Algorithms in C, 3rd Ed., Part 5 - Graph Algorithms. Cambridge MA: Addison-Wesley.
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. Introduction to Algorithms. MIT Press and McGraw-Hill.
- ^ Gabow, H.N. (2000). "Path-based depth-first search for strong and biconnected components". Information Processing Letters. 74: 107–114.
- ^ Gabow, H.N. (2003), "Searching (Ch 10.1)", in Gross, J.L.; Yellen, J. (eds.), Discrete Math. and its Applications: Handbook of Graph Theory, vol. 25, Boca Raton, FL: CRC Press, pp. 953–984