Browse Prior Art Database

SOLVING A CLASS OF GRAPH PROBLEMS ON HYPERCUBE COMPUTERS

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

Publishing Venue

Software Patent Institute

Related People

Sushil Prasad: AUTHOR [+5]

Abstract

This paper presents optimal parallel algorithms on hypercube computers for a class of problems on undirected graphs. The problems include finding a spanning forest, the connected components, a fundamental cycle set, the bridges and checking bipartiteness of a graph. The parallel algorithm for a spanning forest is designed using a divide-and-conquer strategy, and it is used to obtain efficient parallel algorithms for the remaining problems. The input graph is represented by an unordered list of edges. The use of large grain-size and simple merging rules ensures low communication overhead. Communication is restricted to only between neighboring processors. Except the bridge-finding algorithm, all others achieve optimal speedups for dense as well as sparse graphs and each algorithm is optimally scalable up to appropriate number of processors.

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

Page 1 of 19

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

SOLVING A CLASS OF GRAPH PROBLEMS ON HYPERCUBE COMPUTERS

by

Sushil Prasad, Sajal K. Das and Narsingh Deo

CS-TR-87-18 November 1987

Solving a Class of Graph Problems on Hypercube Computers

Sushil Prasad Sajal K. Das Narsingh Deo

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

Abstract

This paper presents optimal parallel algorithms on hypercube computers for a class of problems on undirected graphs. The problems include finding a spanning forest, the connected components, a fundamental cycle set, the bridges and checking bipartiteness of a graph. The parallel algorithm for a spanning forest is designed using a divide-and-conquer strategy, and it is used to obtain efficient parallel algorithms for the remaining problems. The input graph is represented by an unordered list of edges. The use of large grain-size and simple merging rules ensures low communication overhead. Communication is restricted to only between neighboring processors. Except the bridge-finding algorithm, all others achieve optimal speedups for dense as well as sparse graphs and each algorithm is optimally scalable up to appropriate number of processors.

Index Terms: Hypercube computers, graph problems, o ptimal algorithms, spanning forest, connected components, fundamental cycles, bipartite, bridges.

I

1 Introduction

The research directions in parallel algorithms and computations can be broadly categorized as

1. establishing theoretical bounds on the inherent parallel complexity of different prob-lems (and related work), and

2. designing parallel algorithms for such problems implementable on actual parallel machines.

Proving a problem to be in class NC [41 (i.e., it can be solved in poly-logarithmic time using polynomial number of processors), or establishing a lower bound of O(loglogn) for sorting on a concurrent-read and concurrent-write (CRCW) model [31] are examples of the first category. The work in this paper falls into the second category. Due to their wide application in

University of Central Florida Page 1 Dec 31, 1987

Page 2 of 19

SOLVING A CLASS OF GRAPH PROBLEMS ON HYPERCUBE COMPUTERS

communication networks, transportation, VLSI design, code optimization, and other areas of science and engineering, graph problems often require fast solution. We present parallel algorithms for some graph problems on a multiple-instruction and multiple-data (MIMD) hypercube machine model. These machines are message-based fixed interconnection machines with local memory. NCUBE/10 [15], Intel's iPSC [17), and CalTech's Cosmic Cube
[26] are examples of such computers. Another class of parallel computers available are shared- memory machines with a shared-bus or an interconnection network. Encore's Multimax/320 [10] and Sequent's Balance/20000 [27] are two examples of shared-memory bus-based computers while BBN's Butterfly [21 and NYU's Ultracomputer [13] are multi-stage int...