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 J. Cheriyan and K. Mehlhorn [1] and rediscovered in 1999 by H. 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.; Mehlhorn, K. (1996). "Algorithms for dense graphs and networks on the random access computer". Algorithmica. 15: 521–549.
- ^ Sedgewick, R. (2002). Algorithms in C, 3rd Ed., Part 5 - Graph Algorithms. Cambridge MA: Addison-Wesley.
- ^ Cormen, T.H.; Leiserson, C.E.; Rivest, R.L.; Stein, C. (2001). Introduction to Algorithms, 2nd Ed. Cambridge MA: MIT Press, McGraw-Hill Book Company.
- ^ 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