Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Divide-and-Conquer-Based Optimal Parallel Algorithms for Some Graph Problems on EREW PRAM Model

IP.com Disclosure Number: IPCOM000128318D
Original Publication Date: 1987-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 25 page(s) / 58K

Publishing Venue

Software Patent Institute

Related People

Sajal K. Das: AUTHOR [+4]

Abstract

Using an exclusive-read and exclusive-write, parallel random access memory model with a fixed number of processors, we present optimal parallel algorithms for several problems on undirected graphs, namely, finding the connected components, a spanning forest, a fundamental cycle set, the bridges, and checldng bipartiteness of a given graph. The parallel algorithms for computing the connected components and a spanning forest are designed using the divide-and-conquer strategy, and they are in turn used to design efficient parallel algorithms for the remaining three problems. Each of the proposed algorithms achieves optimall speedup for dense as well as sparse graphs, and is optimally scalable up to a certain number of processors. We derive a lower bound on the processor-(time)2 product for each algorithm. The input graph is represented by an unordered list of edges, and the use of simple and elegant data struc-tures avoids memory read- or write-conflicts. Index Terna: EREW PRAM, parallel algorithms, graph problems, optimal algorithms, connected components, spanning forest, fundamental cycles, bridges, bipartite

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 8% of the total text.

Page 1 of 25

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Divide-and-Conquer-Based Optimal Parallel Algorithms for Some Graph Problems on EREW PRAM Model

by

Sajal K. Das and Narsingh Deo

CS-TR-87-16 August 1987 Revised October DIVIDE-AND-CONQUER-BASED OPTIMAL PARALLEL ALGORrrHMS FOR SOME GRAPH PROBLEMS ON EREW PRAM MODEL

Sajal K. Das Narsingh Deo

Department of Computer Science University of Central Florida Orlando, Fl, 32816 - 0001

Abstract

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

Index Terna: EREW PRAM, parallel algorithms, graph problems, optimal algorithms, connected components, spanning forest, fundamental cycles, bridges, bipartite

L INTRODUCTION

Due to their wide applications in communication, transportation, VLSI design, program optimization, and other fields of science and engineering, graph problems often require fast solutions. This paper presents optimal parallel algorithms for five graph problems on a synchronous model of parallel computation. The model is an exclusive-read and exclusive-write (EREW), parallel random access memory (PRAM) consisting of a fixed number p of processors, each equipped with a local memory and a processing unit. Each processor has an identification number, can perform any scalar arithmetic or boolean operation in one time unit, and can read from and write into a common (global) shared memory. Simultaneous reading from or writing into a particu-lar memory cell by more than one processor is not allowed. At any instant, a proces-sor is either masked or executes the same instruction as done by other processors. The necessary synchronization and communication among processors take place via global variables stored in the shared memory. (Two other classes in the PRAM family are concurrent- read and exclusive-write (CREW) model in which processors are allowed to read simultaneously

University of Central Florida Page 1 Dec 31, 1987

Page 2 of 25

Divide-and-Conquer-Based Optimal Parallel Algorithms for Some Graph Problems on EREW PRAM Model

from the same cell but no simultaneous writing...