[Previous [1] [2] [3] [4] [5] [6] [7] [8] [9] [10]

Journal of Inforamtion Science and Engineering, Vol.14 No.2, pp.449-459 (June 1998)
Optimal Algorithms for Interval Graphs

Yue-Li Wang, Kuo-Ching Chiang and Ming-Shing Yu*
Department of Information Management
National Taiwan University of Science and Technology
Taipei, Taiwan 107, R.O.C.
* Department of Applied Mathematics
National Chung-Hsing University
Taichung, Taiwan 402, R.O.C.

In this paper, simple optimal algorithms are presented for solving some problems related to interval graphs. These problems are the connected component problem, the spanning tree problem, the eccentricity problem, and the single source all destinations shortest path problem. All of the above four problems can be solved in linear time if the endpoints of the intervals are sorted. Moreover, our algorithms can be parallelized very easily so that the above problems can be solved in O(log n) time with O(n/log n) processors using the EREW PRAM model.

Keywords: parallel algorithm, spanning tree, connected component, single source all destinations, eccentricity, interval graph, graph theory, EREW PRAM computational model

Received October 19, 1995; revised February 27, 1998.
Communicated by Wen-Lian Hsu.