PARALLEL ALGORITHMS FOR FINDING A SUBOPTIMAL FUNDAMENTAL-CYCLE SET INA GRAPH

An NP-complete problem of finding a fundamental-cycle set of a graph G with 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 a numb er of processors, n is a number of vertices, and m is a number of edge s of G). The algorithms partition an edge and vertex set of G among pr ocessors, respectively, and use a new heuristic method to solve the pr oblem. A message-based tree-connected MIMD computer is assumed as a mo del of parallel computations. The algorithms were implemented for a bi nary tree of 15 transputers, and the experiments were conducted on a w ide range of random graphs. The results show that the vertex set parti tion algorithm with inferior theoretical cost gives better speedups an d finds the fundamental-cycle sets of shorter total lengths as compare d to the edge set partition algorithm.