An Optimal Parallel Algorithm for Constructing a Spanning Tree on Circular Permutation Graphs

Hirotoshi HONMA  Saki HONMA  Shigeru MASUYAMA  

IEICE TRANSACTIONS on Information and Systems   Vol.E92-D   No.2   pp.141-148
Publication Date: 2009/02/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.E92.D.141
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Foundations of Computer Science)
parallel algorithms,  graph algorithms,  circular permutation graphs,  spanning tree,  

Full Text: PDF>>
Buy this Article

The spanning tree problem is to find a tree that connects all the vertices of G. This problem has many applications, such as electric power systems, computer network design and circuit analysis. Klein and Stein demonstrated that a spanning tree can be found in O(log n) time with O(n+m) processors on the CRCW PRAM. In general, it is known that more efficient parallel algorithms can be developed by restricting classes of graphs. Circular permutation graphs properly contain the set of permutation graphs as a subclass and are first introduced by Rotem and Urrutia. They provided O(n2.376) time recognition algorithm. Circular permutation graphs and their models find several applications in VLSI layout. In this paper, we propose an optimal parallel algorithm for constructing a spanning tree on circular permutation graphs. It runs in O(log n) time with O(n/log n) processors on the EREW PRAM.