A Linear-Time Algorithm for Constructing a Spanning Tree on Circular Trapezoid Graphs

Hirotoshi HONMA  Yoko NAKAJIMA  Haruka AOSHIMA  Shigeru MASUYAMA  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E96-A   No.6   pp.1051-1058
Publication Date: 2013/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E96.A.1051
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
design and analysis of algorithms,  intersection graphs,  circular trapezoid graphs,  spanning tree problem,  

Full Text: PDF(1MB)>>
Buy this Article




Summary: 
Given a simple connected graph G with n vertices, the spanning tree problem involves finding a tree that connects all the vertices of G. Solutions to this problem have applications in electrical power provision, computer network design, circuit analysis, among others. It is known that highly efficient sequential or parallel algorithms can be developed by restricting classes of graphs. Circular trapezoid graphs are proper superclasses of trapezoid graphs. In this paper, we propose an O(n) time algorithm for the spanning tree problem on a circular trapezoid graph. Moreover, this algorithm can be implemented in O(log n) time with O(n/log n) processors on EREW PRAM computation model.