Determining Single Connectivity in Directed Graphs
Report ID: TR-390-92Author: Buchsbaum, Adam L. / Carlisle, Martin C.
Date: 1992-09-00
Pages: 7
Download Formats: |Postscript|
Abstract:
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.