Title

Divide-And-Conquer-Based Optimal Parallel Algorithms For Some Graph Problems On Erew Pram Model

Comments

Authors: contact us about adding a copy of your work at STARS@ucf.edu

Keywords

Engineering; Electrical & Electronic

Abstract

Using an exclusive-read and exclusive-write (EREW) parallel random-access memory (PRAM) model with a fixed number of processors, optimal parallel algorithms are presented for several problems on undirected graphs. These problems include finding the connected components, a spanning forest, a fundamental cycle set, the bridges, and checking bipartiteness of a given graph. The algorithms for computing the connected components and a spanning forest are designed using the divide-and-conquer strategy and are used in turn to design efficient algorithms for the remaining three problems. Each of the algorithms achieves optimal speedup for dense as well as sparse graphs, and is optimally scalable up to a certain number of processors. A lower bound on the processor-(time)/sup 2/ product for each algorithm is derived. The input graph is represented by an unordered list of edges, and the use of simple and elegant data structures avoids memory read-conflicts or write-conflicts.

Journal Title

IEEE Transactions on Circuits and Systems

Volume

35

Issue/Number

3

Publication Date

1-1-1988

Document Type

Article

Language

English

First Page

312

Last Page

322

WOS Identifier

WOS:A1988M653400007

ISSN

0098-4094

Share

COinS