DETERMINING UNI-CONNECTIVITY IN DIRECTED-GRAPHS

Authors
BUCHSBAUM AL CARLISLE MC
Citation
Al. Buchsbaum et Mc. Carlisle, DETERMINING UNI-CONNECTIVITY IN DIRECTED-GRAPHS, Information processing letters, 48(1), 1993, pp. 9-12
Citations number
2
Categorie Soggetti
Information Science & Library Science","Computer Applications & Cybernetics
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
48
Issue
1
Year of publication
1993
Pages
9 - 12
Database
ISI
SICI code
0020-0190(1993)48:1<9:DUID>2.0.ZU;2-L
Abstract
We consider the problem of determining whether a directed graph contai ns a pair of vertices connected by two distinct simple paths. A straig htforward implementation using n depth-first searches requires O(nm) t ime on an n-vertex, m-arc digraph; we obtain an O(n2)-time algorithm b y using contraction wherever possible.