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.

深さ優先探索と線形グラフアルゴリズム*

要約。深さ優先探索または「バックトラッキング」を問題を解くための手法として用いる価値を、二つの例によって示す。向き付きグラフの強連結成分を求めるアルゴリズムの改良版と、無向グラフの二重連結成分を求めるアルゴリズムを提示する。両方のアルゴリズムの空間および時間要件は、ある定数 k1,k2,k_1, k_2, および k3k_3 に対して k1V+k2E+k3k_1 V + k_2 E + k_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.