Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-390-92
Determining Single Connectivity in Directed Graphs
Authors: Buchsbaum, Adam L., Carlisle, Martin C.
Date:September 1992
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.