Authors
Citation
S. Khuller, An O(vertical bar V vertical bar(2)) algorithm for single connectedness, INF PROCESS, 72(3-4), 1999, pp. 105-107
Citations number
1
Categorie Soggetti
Information Tecnology & Communication Systems
Journal title
INFORMATION PROCESSING LETTERS
ISSN journal
00200190
→ ACNP
Volume
72
Issue
3-4
Year of publication
1999
Pages
105 - 107
Database
ISI
SICI code
0020-0190(19991126)72:3-4<105:AOBVVB>2.0.ZU;2-Y
Abstract
A directed graph G = (V, E) is said to be singly connected if u curved righ
t arrow v implies that there is at most one simple path from u to v for all
vertices u, u is an element of V. In this paper we design an algorithm to
test a graph for being singly connected that takes O(\V\(2)) steps. (C) 199
9 Published by Elsevier Science B.V. All rights reserved.