Browse Prior Art Database

AN EFFICIENT PARALLEL BICONNECTIVITY ALGORTIHM

IP.com Disclosure Number: IPCOM000128215D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-15
Document File: 12 page(s) / 38K

Publishing Venue

Software Patent Institute

Related People

Robert E. Tarjan: AUTHOR [+4]

Abstract

In this paper we propose a new algorithm for finding the blocks (biconnected components) of an undi-rected graph. A serial implementation runs in 0(n+m) time and space on a graph of n vertices and m edges. A parallel implementation runs in O(log n) time and 0(n+m) space using O(n+m) processors on a concurrent-read, con-current-write parallel RAP1. An alternative implementation runs in O (n2/p) time and 0 (n2) space using any number p < n2/log2n of processors, on a concurrent-read, exclusive-writeparallel RAM. The latter algorithm has optimal speed-up, assuming an adjacency matrix representation of the input. Keywords: Parallel graph algorithm, biconnected corponents, blocks, spanning tree. . 1 AN EFFICIENT PARALLEL BICONNECTIVITY ALGORITHM Robert E. Tarjan ' Bell Laboratories Murray Hill, NJ 07974

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

Page 1 of 12

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

AN EFFICIENT PARALLEL BICONNECTIVITY ALGORTIHM

by

Robert E. Tarjan

' Uzi Vishkin

Technical Report - #69 Ultracomputer Note #51

May 1983

Robert E. Tarjan, Bell Laboratories, Murray Hill, N.J.07974 Uzi Vishkin, Courant Institute, New York University, N.Y. 10012 ~\~u C~) l AN EFFICIENT PARALLEL BICONNECTIVITY ALGORITHM

Robert E. Tarjan Bell Laboratories Murray Hill, NJ 07974.

Uzi Vishkin Courant Institute, New York University New York, NY 10012

May, 1983

Abstract

In this paper we propose a new algorithm for finding the blocks (biconnected components) of an undi-rected graph. A serial implementation runs in 0(n+m) time and space on a graph of n vertices and m edges. A parallel implementation runs in O(log n) time and 0(n+m) space using O(n+m) processors on a concurrent-read, con-current-write parallel RAP1. An alternative implementation runs in O (n2/p) time and 0 (n2) space using any number p < n2/log2n of processors, on a concurrent-read, exclusive-writeparallel RAM. The latter algorithm has optimal speed-up, assuming an adjacency matrix representation of the input.

Keywords: Parallel graph algorithm, biconnected corponents, blocks, spanning tree. . 1

AN EFFICIENT PARALLEL BICONNECTIVITY ALGORITHM

Robert E. Tarjan ' Bell Laboratories Murray Hill, NJ 07974

Uzi Vishkin Courant Institute, New York University New York, NY 10012

1. Introduction

In this paper we consider the problem of computing the blocks (biconnected components) of a given undirected graph G = ME). As a model of parallel computation, we use a concurrent-read, concurrent-write parallel RAM (CRCW PRAM). All the processors have access to a common memory and run synchronously. Simultaneous reading by several processors from the same memory location is allowed as well as simul-taneous writing. In the latter case one processor

New York University Page 1 Dec 31, 1983

Page 2 of 12

AN EFFICIENT PARALLEL BICONNECTIVITY ALGORTIHM

succeeds but we do not know in advance which. This model, used for instance in [SV 82], is a member of a family of models for parallel computation. (See [BE 82], [SV 81], [V 81a].) We propose a new algorithm for finding blocks. We discuss three implementations of the algorithm:

1. A linear-time sequential implementation. 2. A parallel implementation using O(log n) time, 0(n+m) space, and O(n+m) processors, where

(Equation Omitted)

3. An alternative parallel implementation using O(n2/p) time, O(n2) space, and any number p < n2/log2n of processors. _ 2

This implementation uses a concurrent-read, exclusive-write parallel RAM (CREW PRAM). This model differs from the CRCW PRAM in not allowing simultaneous writing by more than one processor into the same memory location. The speed-up of this implementation is optimal in the sense that the time-processor product is 0(n2), which is the time required by an optimal sequential algorithm if the input representation is an adjacency matrix.

Implementation...