-
Isreal Cidon.
Yet another distributed depth-first-search algorithm.
Information Processing Letters,
26(6):301--305,
1988.
[PDF
]
Keywords:
Distributed system,
distributed algorithm,
asynchronous,
depth-first-search.
| Abstract: |
A new distributed depth-first-search algorithm is presented whose communication and time complexities are bounded by 3|E| and 2|V|, respectively. |
| Comments: |
This formulation contains an error. See the corrected result in Tsin's {\e
m Some remarks on distributed depth-first search}. |
@Article{CidonDFS88,
author = {Isreal Cidon},
title = {Yet another distributed depth-first-search algorithm},
journal = {Information Processing Letters},
volume = {26},
number = {6},
year = {1988},
pages = {301--305},
publisher = {Elsevier North-Holland, Inc.},
keywords = {Distributed system; distributed algorithm; asynchronous; depth-first-search},
pdf = {PAPERS/CidonDFS88.pdf},
abstract = {A new distributed depth-first-search algorithm is presented whose communication and time complexities are bounded by $3|E|$ and $2|V|$, respectively.},
comments = {This formulation contains an error. See the corrected result in Tsin's {\em Some remarks on distributed depth-first search}.}
}
-
James R. Driscoll,
Harold N. Gabow,
Ruth Shrairman,
and Robert E. Tarjan.
Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation.
Communications of the ACM,
31(11):1343--1354,
1988.
[PDF
]
Keywords:
Single-source shortest paths,
EREW,
PRAM.
@Article{DriscollGabowShrairman88,
author = {James R. Driscoll and Harold N. Gabow and Ruth Shrairman and Robert E. Tarjan},
title = {Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation},
journal = {Communications of the {ACM}},
volume = {31},
number = {11},
year = {1988},
issn = {0001-0782},
pages = {1343--1354},
publisher = {ACM Press},
keywords = {Single-source shortest paths, EREW, PRAM},
pdf = {PAPERS/DriscollGabowShrairman88.pdf}
}
-
Hillel Gazit and Gary L. Miller.
An improved parallel algorithm that computes the BFS numbering of a directed graph.
Information Processing Letters,
28(2):61--65,
1988.
[PDF
]
Keywords:
Breadth-first search,
fast matrix multiplication,
parallel algorithm,
EREW,
PRAM.
| Abstract: |
This paper presents a parallel algorithm that computes the breadth-first search (BFS) numbering of a directed graph in O(log^2 n) time using M(n) processors on the exclusive-read exclusive-write (EREW) parallel random access machine (PRAM) model, where M(n) denotes the number of processors needed to multiply two n \times n integer matrices over the ring ({\mathbb Z}, +, x) in O(log n) time. The best known bound for M(n) is O(n^2.376) (Coppersmith and Winograd, 1987). The algorithm presented in their paper uses fewer processors than the classical algorithm for BFS that employs matrix powering over the semiring (dioid) ({\mathbb N}, min, +), using O(log n) time and O(n^3) processors on the concurrent-read concurrent-write (CRCW) model, or using O(log^2 n) time and n^3log n processors on the EREW model. |
@Article{GazitMillerBFS88,
author = {Hillel Gazit and Gary L. Miller},
title = {An improved parallel algorithm that computes the BFS numbering of a directed graph},
journal = {Information Processing Letters},
volume = {28},
number = {2},
year = {1988},
issn = {0020-0190},
pages = {61--65},
publisher = {Elsevier North-Holland, Inc.},
keywords = {Breadth-first search; fast matrix multiplication; parallel algorithm; EREW; PRAM},
pdf = {PAPERS/GazitMillerBFS88.pdf},
abstract = {This paper presents a parallel algorithm that computes the breadth-first search (BFS) numbering of a directed graph in $O(log^2 n)$ time using $M(n)$ processors on the exclusive-read exclusive-write (EREW) parallel random access machine (PRAM) model, where $M(n)$ denotes the number of processors needed to multiply two $n \times n$ integer matrices over the ring $({\mathbb Z}, +, x)$ in $O(log n)$ time. The best known bound for $M(n)$ is $O(n^2.376)$ (Coppersmith and Winograd, 1987). The algorithm presented in their paper uses fewer processors than the classical algorithm for BFS that employs matrix powering over the semiring (dioid) $({\mathbb N}, min, +)$, using $O(log n)$ time and $O(n^3)$ processors on the concurrent-read concurrent-write (CRCW) model, or using $O(log^2 n)$ time and $n^3log n$ processors on the EREW model.}
}