|
TR-390-92
Determining Single Connectivity in Directed Graphs |
|
| Authors: | Buchsbaum, Adam L., Carlisle, Martin C. |
| Date: | September 1992 |
| Pages: | 7 |
| Download Formats: | [Postscript] |
In this paper, we consider the problem of determining whether or not a directed graph contains a pair of vertices connected by two distinct simple paths; if it does not, we say it is {em singly connected}. A straightforward implementation using $n$ depth first searches requires $O(nm)$ time on an $n$-vertex, $m$-arc digraph; we obtain an $O(n^2)$ time algorithm by using contraction wherever possible. |
|