ID:
publications-4381
Type:
article
Year:
1971
Authors:
Tarjan, Robert E. and Tarjan, Robert E.
Title:
Depth-first search and linear graph algorithms
Venue/Journal:
DOI:
10.1109/swat.1971.10
Research type:
Water System:
Technical Focus:
Abstract:
The value of depth-first search or "backtracking" as a technique for solving graph problems is illustrated by two examples. An algorithm for finding the biconnected components of an undirected graph and an improved version of an algorithm for finding the strongly connected components of a directed graph are presented. The space and time requirements of both algorithms are bounded by k1V + k2E + k3 for some constants k1, k2, and k3, where V is the number of vertices and E is the number of edges of the graph being examined.
Link with Projects:
Link with Tools:
Related policies:
ID:
