Parallel algorithms for finding a suboptimal

fundamental-cycle set in a graph?

Zbigniew J. Czechy Marek Konopkaz

Institute of Computer Science, Silesia University of Technology
Pstrowskiego 16, 44-100 Gliwice, Poland
E-mail: fzjc,mkonopkag@gleto3.gliwice.edu.pl

Bohdan S. Majewski
Department of Computer Science
Key Centre for Software Technology
University of Queensland
St. Lucia, Queensland 4072
Australia
E-mail: bohdan@cs.uq.oz.au

Abstract

An NP-complete problem of finding a fundamental-cycle set of a graph G with the minimum total length is considered. Two parallel algorithms of O(n2=p+n log n log p) and O(m + n2=p + n log (n=p) + n log p) costs to find a suboptimal solution to this problem are presented (p is the number of processors, n is the number of vertices, and m is the number of edges of G). The algorithms partition the edge and the vertex set of G among processors, respectively, and use a new heuristic method to solve the problem. A message-based tree-connected MIMD computer is assumed as the model of parallel computations.

The algorithms were implemented for a binary tree of 15 transputers, and the experiments on a wide range of random graphs were conducted. The results show that the vertex set partition algorithm with an inferior theoretical cost gives a better speedup and finds fundamental-cycle sets of the shorter total lengths in comparison to the edge set partition algorithm.

Key words. Design and analysis of parallel algorithms, complexity of parallel computations, distributed memory architectures, transputer-based systems

?To appear in Parallel Computing
ySupported by the Committee for Scientific Research (grant PB-907/3/91).
zSupported by the Tempus programme (grant IMG-PLS-0676-90).