On the parallel complexity of digraph reachability

Samir Khuller; Uzi Vishkin

doi:10.1016/0020-0190(94)00153-7

On the parallel complexity of digraph reachability

Samir Khuller^*, Uzi Vishkin

^*Corresponding author for this work

Computer Science

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

2 Scopus citations

Abstract

We formally show that the directed graph reachability problem can be reduced to several problems using a linear number of processors; hence an efficient parallel algorithm to solve any of these problems would imply an efficient parallel algorithm for the directed graph reachability problem. This formally establishes that all these problems are at least as hard as the s-t reachability problem.

Original language	English (US)
Pages (from-to)	239-241
Number of pages	3
Journal	Information Processing Letters
Volume	52
Issue number	5
DOIs	https://doi.org/10.1016/0020-0190(94)00153-7
State	Published - Dec 9 1994

Funding

* Corresponding author. Email: [email protected]. Research supported by NSF Research Initiation Award CCR-9307462. Part of this work was done while this author was with UMIACS and supported by NSF grant CCR-8906949. ’ Email: [email protected]. Research supported by NSF grant CCR-9111348.

Keywords

Combinatorial problems
Parallel algorithms

ASJC Scopus subject areas

Theoretical Computer Science
Signal Processing
Information Systems
Computer Science Applications

Access to Document

10.1016/0020-0190(94)00153-7

Cite this

@article{08b593f635c443d392854665219618c6,

title = "On the parallel complexity of digraph reachability",

abstract = "We formally show that the directed graph reachability problem can be reduced to several problems using a linear number of processors; hence an efficient parallel algorithm to solve any of these problems would imply an efficient parallel algorithm for the directed graph reachability problem. This formally establishes that all these problems are at least as hard as the s-t reachability problem.",

keywords = "Combinatorial problems, Parallel algorithms",

author = "Samir Khuller and Uzi Vishkin",

note = "Funding Information: * Corresponding author. Email: [email protected]. Research supported by NSF Research Initiation Award CCR-9307462. Part of this work was done while this author was with UMIACS and supported by NSF grant CCR-8906949. {\textquoteright} Email: [email protected]. Research supported by NSF grant CCR-9111348.",

year = "1994",

month = dec,

day = "9",

doi = "10.1016/0020-0190(94)00153-7",

language = "English (US)",

volume = "52",

pages = "239--241",

journal = "Information Processing Letters",

issn = "0020-0190",

publisher = "Elsevier",

number = "5",

}

TY - JOUR

T1 - On the parallel complexity of digraph reachability

AU - Khuller, Samir

AU - Vishkin, Uzi

N1 - Funding Information: * Corresponding author. Email: [email protected]. Research supported by NSF Research Initiation Award CCR-9307462. Part of this work was done while this author was with UMIACS and supported by NSF grant CCR-8906949. ’ Email: [email protected]. Research supported by NSF grant CCR-9111348.

PY - 1994/12/9

Y1 - 1994/12/9

N2 - We formally show that the directed graph reachability problem can be reduced to several problems using a linear number of processors; hence an efficient parallel algorithm to solve any of these problems would imply an efficient parallel algorithm for the directed graph reachability problem. This formally establishes that all these problems are at least as hard as the s-t reachability problem.

AB - We formally show that the directed graph reachability problem can be reduced to several problems using a linear number of processors; hence an efficient parallel algorithm to solve any of these problems would imply an efficient parallel algorithm for the directed graph reachability problem. This formally establishes that all these problems are at least as hard as the s-t reachability problem.

KW - Combinatorial problems

KW - Parallel algorithms

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

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

U2 - 10.1016/0020-0190(94)00153-7

DO - 10.1016/0020-0190(94)00153-7

M3 - Article

AN - SCOPUS:0028769703

SN - 0020-0190

VL - 52

SP - 239

EP - 241

JO - Information Processing Letters

JF - Information Processing Letters

IS - 5

ER -

On the parallel complexity of digraph reachability

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this