Depth-First Search and Linear Graph Algorithms

Robert Tarjan, 1972, SIAM Journal on Computing

About this paperEnglishTiếng Việt日本語beside Englishbeside Tiếng Việtbeside 日本語

This paper is under a licence that does not allow it to be reproduced, so what is here is its front matter and a short abstract. Read it at the publisher's page.

深度优先搜索与线性图算法*

摘要。通过两个例子说明深度优先搜索或“回溯”作为求解问题的一种技术的价值。给出一种改进的求有向图强连通分量的算法，以及一种求无向图双连通分量的算法。这两种算法的空间和时间需求均有界于k1V+k2E+k3k_1 V + k_2 E + k_3，其中k1,k2,k_1, k_2,和k3k_3为某些常数，VV为所考察图的顶点数，EE为所考察图的边数。

References

  1. B. L. FOX AND D. M. LANDY, An algorithm for identifying the ergodic subchains and transient states of a stochastic matrix, Comm. ACM, 11 (1968), pp. 619–621.
  2. S. W. GOLOMB AND L. D. BAUMERT, Backtrack programming, J. ACM, 12 (1965), pp. 516–524.
  3. F. HARARY, Graph Theory, Addison-Wesley, Reading, Mass., 1969.
  4. J. HOPCROFT AND R. TARJAN, Efficient algorithms for graph manipulation, Tech. Rep. 207, Computer Science Department, Stanford University, Stanford, Calif., 1971.
  5. ———, A V^2 algorithm for determining isomorphism of planar graphs, Information Processing Letters, 1 (1971), pp. 32–34.
  6. ———, Planarity testing in V log V steps: Extended abstract, Tech. Rep. 201, Computer Science Department, Stanford University, Stanford, Calif., 1971.
  7. J. HOPCROFT, An N log N algorithm for isomorphism of planar triply connected graphs, Tech. Rep. 192, Computer Science Department, Stanford University, Stanford, Calif., 1971.
  8. J. HOPCROFT AND R. TARJAN, Isomorphism of planar graphs, IBM Symposium on Complexity of Computer Computations, Yorktown Heights, N.Y., March, 1972, to be published by Plenum Press.
  9. J. HOPCROFT AND J. ULLMAN, A linear list-merging algorithm, Tech. Rep. 71-111, Cornell University Computer Science Department, Ithaca, N.Y., 1971.
  10. I. MUNRO, Efficient determination of the strongly connected components and transitive closure of a directed graph, Department of Computer Science, University of Toronto, 1971.
  11. N. J. NILSON, Problem Solving Methods in Artificial Intelligence, McGraw-Hill, New York, 1971.
  12. K. PATON, An algorithm for the blocks and cutnades of a graph, Comm. ACM, 14 (1971), pp. 468–475.
  13. P. W. PURDOM, A transitive closure algorithm, Tech. Rep. 33, Computer Sciences Department, University of Wisconsin, Madison, 1968.
  14. R. W. SHIREY, Implementation and analysis of efficient graph planarity testing algorithms, Doctoral thesis, Computer Sciences Department, University of Wisconsin, Madison, 1969.
  15. R. TARJAN, An efficient planarity algorithm, Tech. Rep. 244, Computer Science Department, Stanford University, Stanford, Calif., 1971.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8. Translated into 中文 by gpt-5, against glossary version 6. Translated from the English.