Browse Prior Art Database

An Efficient Parallel Strong Orientation Disclosure Number: IPCOM000149422D
Original Publication Date: 1984-Feb-29
Included in the Prior Art Database: 2007-Apr-01

Publishing Venue

Software Patent Institute

Related People

Vishkin, Uzi: AUTHOR [+2]


An Efficient Parallel Strong Orientation (February 1984) Technical Report 109

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 15% of the total text.

Page 1 of 14

An Efficient Parallel Strong Orientation
(February 1984)

Technical Report 109

Ultracomputer Note 67

            Uzi Vishkin
of Computer Science
Courant Institute of Mathematical Sciences
New York University
251 Mercer St., New York, NY 10012

    *This research was supported by DOE grant DE-.AC02-76E~03077 and by NSF grant


[This page contains 1 picture or other non-text object]

Page 2 of 14

[This page contains 1 picture or other non-text object]

Page 3 of 14

    The family of models of computation used in this paper is the parallel
random-access-machines (PRAMS). All members o.E this family employ p synchronous
processors all having access to a common memory. We mention 3 members of the PRAM
family in descending order of strength. In a concurrent-read concurrent-write
(CRCW) PRAM simultaneous reading from the sam; memory location is allowed as well
as simultaneous writing. In the latter case the lowest numbered processor
succeeds. A concurrent-read exclusive-write (CREW) PRAM allows simultaneous
reading into the same memory location but not simultaneous writing. An.EREW PRAM
does not allow simultaneous reading or writing. See [vi-831 for a recent survey
of results concerning the PRAM family.

    Recall that a bridge in a connected graph is an edge whose removal
disconnects the graph and a digraph is strongly connected if for every two
vertices u and v there is a directed path from u to v. The following problem is
considered. Inpuc. A connected bridgeless undirected graph G=(v,E), lVl=n,
\~l=rn. The scrong o~&e-n-tat$o$ problem.

              - Assign directions to its edges so that
the resulting digraph is strongly connected. It is known that such strong
orientation exists iff the input graph is connected and bridgeless. [At-841
indicates that this problem has a simple linear time serial solution: Apply
depth-first search to the graph. Orient tree edges away from the root and back
edges towards the root. Since depth-first search seems tb be inherently serial
(see [R-831 for some evidence) another approach is required for designing
efficient parallel algorithms. [At-841 gave an O(log n) time algorithm for this
problem using n3 processors on a CRCW PRAM. Atallah's algorithm runs in
~ ( n ~ / ~

    + log2n) time using p processors on a CREW PRAM. Our algorithm runs in
O(1og n) time using only ni-m processors on a CRCW PRAM. An alternative

                                2 2 2
implementation of the algorithm runs in 0(n /p) time using p ( n /log n processors

[This page contains 1 picture or other non-text object]

Page 4 of 14

on an CREW PRAM. This is optimal for dense graphs. A very high-level description
of our algorithm is close to Atallah's algorithm. However, only a complete and
drastic change in the way parallelism is approached allows the
improvements in efficiency. Algorithmic methods that reduce the number of
processors without changing the running time are of great importa...