research-article

Depth-First Search and Linear Graph Algorithms

Author:

Robert TarjanAuthors Info & Claims

SIAM Journal on Computing, Volume 1, Issue 2

Pages 146 - 160

https://doi.org/10.1137/0201010

Published: 01 June 1972 Publication History

Abstract

The value of depth-first search or “backtracking” as a technique for solving problems is illustrated by two examples. An improved version of an algorithm for finding the strongly connected components of a directed graph and at algorithm for finding the biconnected components of an undirect graph are presented. The space and time requirements of both algorithms are bounded by $k_1 V + k_2 E + k_3 $ for some constants $k_1,k_2 $, and $k_3 $, where V is the number of vertices and E is the number of edges of the graph being examined.

References

[1]

B. L. Fox, D. M. Landy, An algorithm for identifying the ergodic subchains and transient states of a stochastic matrix, Comm. ACM, 11 (1968), 619–621

Digital Library

[2]

Solomon W. Golomb, Leonard D. Baumert, Backtrack programming, J. Assoc. Comput. Mach., 12 (1965), 516–524

Digital Library

[3]

Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London, 1969ix+274

[4]

J. Hopcroft, R. Tarjan, Efficient algorithms for graph manipulation, Tech. Rep., 207, Computer Science Department, Stanford University, Stanford, Calif., 1971

[5]

J. Hopcroft, R. Tarjan, A $V^{2}$ algorithm for determining isomorphism of planar graphs, Information Processing Letters, 1 (1971), 32–34

[6]

J. Hopcroft, R. Tarjan, Planarity testing in VlogV steps: Extended abstract, Tech. Rep., 201, Computer Science Department, Stanford University, Stanford, Calif., 1971

[7]

J. Hopcroft, An NlogN algorithm for isomorphism of planar triply connected graphs, Tech. Rep., 192, Computer Science Department, Stanford University, Stanford, Calif., 1971

[8]

J. E. Hopcroft, R. E. Tarjan, Isomorphism of planar graphsComplexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N. Y., 1972), Plenum, New York, 1972, 131–152, 187–212

[9]

J. Hopcroft, 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]

Keith Paton, An algorithm for the blocks and cutnodes of a graph, Comm. ACM, 14 (1971), 468–475

Digital Library

[13]

P. W. Purdom, A transitive closure algorithm, Tech. Rep., 33, Computer Sciences Department, University of Wisconsin, Madison, 1968

[14]

R. W. Shirey, Masters Thesis, 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

Cited By

Zhang YLi RZhang QQin HWang G(2024)Efficient Algorithms for Density Decomposition on Large Static and Dynamic GraphsProceedings of the VLDB Endowment10.14778/3681954.368197417:11(2933-2945)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681974
Chen XShi JPeng YLin WWang SZhang W(2024)Minimum Strongly Connected Subgraph Collection in Dynamic GraphsProceedings of the VLDB Endowment10.14778/3648160.364817317:6(1324-1336)Online publication date: 3-May-2024
https://doi.org/10.14778/3648160.3648173
Cook WHeld SHelsgaun K(2024)Constrained Local Search for Last-Mile RoutingTransportation Science10.1287/trsc.2022.118558:1(12-26)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/trsc.2022.1185
Show More Cited By

Index Terms

Depth-First Search and Linear Graph Algorithms

Index terms have been assigned to the content through auto-classification.

Recommendations

Some forbidden subgraph conditions for a graph to have a k-contractible edge
Special issue: Combinatorics 2000

An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. Let K"n^- stand for the graph obtained from K"n by removing one edge. Let G be a k-connected graph (k>=5). It is known that if ...
A parallel search algorithm for directed acyclic graphs
Abstract
A parallel algorithm for depth-first searching of a directed acyclic graph (DAG) on a shared memory model of a SIMD computer is proposed. The algorithm uses two parallel tree traversal algorithms, one for the preorder traversal and the other for ...
The bondage and connectivity of a graph

Let G =(V,E) be a simple graph. A subset S of V is a dominating set of G if for any vertex v ∈ V - S, there exists some vertex u ∈ S such that uv ∈ E(G). The domination number, denoted by γ(G), is the cardinality of a minimum dominating set of G. The ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image SIAM Journal on Computing

SIAM Journal on Computing Volume 1, Issue 2

Jun 1972

72 pages

ISSN:0097-5397

DOI:10.1137/smjcat.1972.1.issue-2

Issue’s Table of Contents

Copyright © 1972 Society for Industrial and Applied Mathematics.

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 01 June 1972

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

268
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Zhang YLi RZhang QQin HWang G(2024)Efficient Algorithms for Density Decomposition on Large Static and Dynamic GraphsProceedings of the VLDB Endowment10.14778/3681954.368197417:11(2933-2945)Online publication date: 1-Jul-2024
https://dl.acm.org/doi/10.14778/3681954.3681974
Chen XShi JPeng YLin WWang SZhang W(2024)Minimum Strongly Connected Subgraph Collection in Dynamic GraphsProceedings of the VLDB Endowment10.14778/3648160.364817317:6(1324-1336)Online publication date: 3-May-2024
https://doi.org/10.14778/3648160.3648173
Cook WHeld SHelsgaun K(2024)Constrained Local Search for Last-Mile RoutingTransportation Science10.1287/trsc.2022.118558:1(12-26)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/trsc.2022.1185
Jagabathula SRusmevichientong PVenkataraman AZhao X(2024)Estimating Large-Scale Tree Logit ModelsOperations Research10.1287/opre.2023.247972:1(257-276)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/opre.2023.2479
Zhou YLi JHao JGlover F(2024)Detecting Critical Nodes in Sparse Graphs via “Reduce-Solve-Combine” Memetic SearchINFORMS Journal on Computing10.1287/ijoc.2022.013036:1(39-60)Online publication date: 1-Jan-2024
https://dl.acm.org/doi/10.1287/ijoc.2022.0130
Núñez-Molina CMesejo PFernández-Olivares J(2024)A Review of Symbolic, Subsymbolic and Hybrid Methods for Sequential Decision MakingACM Computing Surveys10.1145/366336656:11(1-36)Online publication date: 28-Jun-2024
https://dl.acm.org/doi/10.1145/3663366
Beyer DKettl MLemberger T(2024)Decomposing Software Verification using Distributed Summary SynthesisProceedings of the ACM on Software Engineering10.1145/36607661:FSE(1307-1329)Online publication date: 12-Jul-2024
https://dl.acm.org/doi/10.1145/3660766
Lei YBossut CSui YZhang Q(2024)Context-Free Language Reachability via Skewed TabulationProceedings of the ACM on Programming Languages10.1145/36564518:PLDI(1830-1853)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656451
Parkinson MClebsch SWrigstad TBond MLee JPayer H(2024)Reference Counting Deeply Immutable Data Structures with Cycles: An Intellectual AbstractProceedings of the 2024 ACM SIGPLAN International Symposium on Memory Management10.1145/3652024.3665507(131-141)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3652024.3665507
Xu PLei YSui YXue J(2024)Iterative-Epoch Online Cycle Elimination for Context-Free Language ReachabilityProceedings of the ACM on Programming Languages10.1145/36498628:OOPSLA1(1437-1462)Online publication date: 29-Apr-2024
https://dl.acm.org/doi/10.1145/3649862
Show More Cited By

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents