O(|V|2) algorithm for single connectedness

Samir Khuller

doi:10.1016/s0020-0190(99)00135-0

O(|V|²) algorithm for single connectedness

Samir Khuller

Computer Science

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

A directed graph G = (V, E) is said to be singly connected if uqqv implies that there is at most one simple path from u to v for all vertices u, v∈V. An algorithm is designed to test a graph for being singly connected that takes O(|V|²) steps.

Original language	English (US)
Pages (from-to)	105-107
Number of pages	3
Journal	Information Processing Letters
Volume	72
Issue number	3
DOIs	https://doi.org/10.1016/s0020-0190(99)00135-0
State	Published - Nov 26 1999

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/s0020-0190(99)00135-0

Cite this

@article{58acc41387e1409a8fe35647e440c2be,

title = "O(|V|2) algorithm for single connectedness",

abstract = "A directed graph G = (V, E) is said to be singly connected if uqqv implies that there is at most one simple path from u to v for all vertices u, v∈V. An algorithm is designed to test a graph for being singly connected that takes O(|V|2) steps.",

author = "Samir Khuller",

year = "1999",

month = nov,

day = "26",

doi = "10.1016/s0020-0190(99)00135-0",

language = "English (US)",

volume = "72",

pages = "105--107",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - O(|V|2) algorithm for single connectedness

AU - Khuller, Samir

PY - 1999/11/26

Y1 - 1999/11/26

N2 - A directed graph G = (V, E) is said to be singly connected if uqqv implies that there is at most one simple path from u to v for all vertices u, v∈V. An algorithm is designed to test a graph for being singly connected that takes O(|V|2) steps.

AB - A directed graph G = (V, E) is said to be singly connected if uqqv implies that there is at most one simple path from u to v for all vertices u, v∈V. An algorithm is designed to test a graph for being singly connected that takes O(|V|2) steps.

UR - http://www.scopus.com/inward/record.url?scp=0033607396&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033607396&partnerID=8YFLogxK

U2 - 10.1016/s0020-0190(99)00135-0

DO - 10.1016/s0020-0190(99)00135-0

M3 - Article

AN - SCOPUS:0033607396

SN - 0020-0190

VL - 72

SP - 105

EP - 107

JO - Information Processing Letters

JF - Information Processing Letters

IS - 3

ER -

O(|V|²) algorithm for single connectedness

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this