Depth-First Search and Linear Graph Algorithms
SIAM Journal on Computing · 1972 · 6,441 citations
No retraction on record in OpenAlex.Check Crossref now
Cite this paper
Tarjan, R. E. (1972). Depth-first search and linear graph algorithms. SIAM Journal on Computing, 1(2), 146–160. https://doi.org/10.1137/0201010
In text: (Tarjan, 1972)
Ask a question about this research
One question, free, no account. Anchorcite finds the papers, checks each against Crossref and links every sentence of the answer to the passage it comes from.
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.
Related papers
Metadata from OpenAlex (CC0). Citations are generated from the published record.