Depth-First Search and Linear Graph Algorithms

Robert Tarjan, 1972, SIAM Journal on Computing

About this paper中文日本語

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.

Tiếng Việt
English

TÌM KIẾM THEO CHIỀU SÂU VÀ CÁC THUẬT TOÁN ĐỒ THỊ TUYẾN TÍNH*

Tóm tắt. Giá trị của tìm kiếm theo chiều sâu hoặc “quay lui” như một kỹ thuật để giải quyết các bài toán được minh họa bằng hai ví dụ. Một phiên bản cải tiến của một thuật toán để tìm các thành phần liên thông mạnh của một đồ thị có hướng và một thuật toán để tìm các thành phần liên thông kép của một đồ thị vô hướng được trình bày. Các yêu cầu về không gian và thời gian của cả hai thuật toán bị chặn bởi k1V+k2E+k3k_1 V + k_2 E + k_3 với một số hằng số k1,k2,k_1, k_2, và k3k_3, trong đó VV là số nút và EE là số cạnh của đồ thị đang được kiểm tra.

This section is missing here.

Robert Tarjan†

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 Tiếng Việt by gpt-5, against glossary version 7. Translated from the English.

Read off the page by a vision model reading the page images using olmOCR-2-7B-1025-FP8.