A parallel algorithm for the Steiner tree problem

Author

Makki, Kia ; Been, K. ; Pissinou, Niki

Author_Institution

Dept. of Comput. Sci., Nevada Univ., Las Vegas, NV, USA

fYear

1993

fDate

27-29 May 1993

Firstpage

380

Lastpage

384

Abstract

The Steiner problem in graphs is to find the minimum cost tree which spans at least a given subset of V, where V is the set of vertices in the graph. This problem has a wide variety of practical applications, including wire routing in physical VLSI design. Since the problem is NP-complete, much work has been devoted to developing approximate solutions such as the one proposed by V.J. Rayward-Smith (1988). In this paper, we identify the Rayward-Smith´s algorithm as being appropriate for parallelization, and describe a parallel implementation of that algorithm. We also show that linear speedup is achievable on the PRAM model with the number of processors p⩽|V|

Keywords

computational complexity; parallel algorithms; random-access storage; tree data structures; NP-complete; PRAM model; Steiner tree problem; minimum cost tree; parallel algorithm; physical VLSI design; vertices; wire routing; Communication networks; Computer science; Costs; Parallel algorithms; Phase change random access memory; Routing; Steiner trees; Tree graphs; Very large scale integration; Wire;

fLanguage

English

Publisher

ieee

Conference_Titel

Computing and Information, 1993. Proceedings ICCI '93., Fifth International Conference on

Conference_Location

Sudbury, Ont.

Print_ISBN

0-8186-4212-2

Type

conf

DOI

10.1109/ICCI.1993.315344

Filename

315344