Quick links

Determining Single Connectivity in Directed Graphs

Report ID:
TR-390-92
Date:
August 1992
Pages:
7
Download Formats:

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.

Follow us: Facebook Twitter Linkedin