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 compo...Show MoreMetadata
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.
Date of Conference: 13-15 October 1971
Date Added to IEEE Xplore: 18 July 2008
Print ISSN: 0272-4847