×

zbMATH — the first resource for mathematics

Path-based depth-first search for strong and biconnected components. (English) Zbl 1339.68301
From the introduction: Depth-first search, as developed by Tarjan and co-authors, is a fundamental technique of efficient algorithm design for graphs [R. Tarjan, SIAM J. Comput. 1, 146–160 (1972; Zbl 0251.05107)]. This note presents depth-first search algorithms for two basic problems, strong and biconnected components. Previous algorithms either compute auxiliary quantities based on the depth-first search tree (e.g., LOWPOINT values) or require two passes. We present one-pass algorithms that only maintain a representation of the depth-first search path. This gives a simplified view of depth-first search without sacrificing efficiency.

MSC:
68W05 Nonnumerical algorithms
05C85 Graph algorithms (graph-theoretic aspects)
Software:
GraphBase
PDF BibTeX XML Cite
Full Text: DOI Link
References:
[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0207.01701
[2] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., Data structures and algorithms, (1983), Addison-Wesley Reading, MA · Zbl 0257.68065
[3] Berge, C., Hypergraphs: combinatorics of finite sets, (1989), North-Holland New York · Zbl 0674.05001
[4] Brassard, G.; Bratley, P., Algorithmics: theory & practice, (1988), Prentice-Hall Englewood Cliffs, NJ · Zbl 0643.68003
[5] Brassard, G.; Bratley, P., Fundamentals of algorithmics, (1996), Prentice-Hall Englewood Cliffs, NJ · Zbl 0847.68046
[6] Cormen, T.H.; Leiserson, C.E.; Rivest, R.L., Introduction to algorithms, (1990), McGraw-Hill New York · Zbl 1158.68538
[7] Even, S., Graph algorithms, (1979), Computer Science Press Potomac, MD · Zbl 0441.68072
[8] Gabow, H.N., Path-based depth-first search for strong and biconnected components, (2000), Dept. of Computer Science, University of Colorado at Boulder, Tech. Report CU-CS-890-99, revised version · Zbl 1339.68301
[9] Gabow, H.N.; Tarjan, R.E., A linear-time algorithm for a special case of disjoint set union, J. comput. system sci., Vol. 30, 2, 209-221, (1985) · Zbl 0572.68058
[10] Hopcroft, J.E.; Tarjan, R.E., Dividing a graph into triconnected components, SIAM J. comput., Vol. 2, 135-158, (1973) · Zbl 0281.05111
[11] Hopcroft, J.E.; Tarjan, R.E., Efficient planarity testing, J. ACM, Vol. 21, 4, 549-568, (1974) · Zbl 0307.68025
[12] Harary, F., Graph theory, (1969), Addison-Wesley Reading, MA · Zbl 0797.05064
[13] Horowitz, E.; Sahni, S.; Rajasekaran, S., Computer algorithms, (1998), Computer Science Press New York
[14] Knuth, D.E., The Stanford graphbase: A platform for combinatorial computing, (1993), Addison-Wesley Reading, MA · Zbl 0806.68121
[15] Lovász, L., Combinatorial problems and exercises, (1993), North-Holland New York, 2nd edn. · Zbl 0785.05001
[16] Manber, U., Introduction to algorithms: A creative approach, (1989), Addison-Wesley Reading, MA · Zbl 0825.68397
[17] Mehlhorn, K., Data structures and algorithms 2: graph algorithms and NP-completeness, (1984), Springer New York · Zbl 0556.68002
[18] Munro, I., Efficient determination of the strongly connected components and transitive closure of a directed graph, (1971), Department of Computer Science, University of Toronto
[19] Purdom, P.W., A transitive closure algorithm, (1968), Computer Sciences Department, University of Wisconsin Madison, WI, Tech. Report 33 · Zbl 0164.48504
[20] Robbins, H.E., A theorem on graphs with an application to a problem of traffic control, Amer. math. monthly, Vol. 46, 281-283, (1939) · Zbl 0021.35703
[21] Sedgewick, R., Algorithms in C, (1990), Addison-Wesley Reading, MA · Zbl 0798.68002
[22] Sharir, M., A strong-connectivity algorithm and its application in data flow analysis, Comput. math. appl., Vol. 7, 1, 67-72, (1981) · Zbl 0443.68046
[23] Tarjan, R.E., Depth-first search and linear graph algorithms, SIAM J. comput., Vol. 1, 2, 146-160, (1972) · Zbl 0251.05107
[24] Tarjan, R.E., Efficiency of a good but not linear set union algorithm, J. ACM, Vol. 22, 2, 215-225, (1975) · Zbl 0307.68029
[25] Weiss, M.A., Data structures and algorithm analysis in C++, (1999), Addison-Wesley Reading, MA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.