Taong-Wann Kao and Shi-Jinn Horng#
Department of Electronic Engineering
Kuang Wu Institute of Technology and Commerce.
Peito, Taipei, Taiwan, Republic of China
# Department of Electrical Engineering
National Taiwan Institute of Technology
Taipei, Taiwan, Republic of China
In this paper, we shall present an algorithm for computing the ranges of the dominators and immediate dominator of each vertex of an interval graph. We first give an optimal O(n logn) time sequential algorithm for this problem if the endpoints of the intervals are unsorted. If the endpoints are presorted, our algorithm can be solved in O(n) time. The sequential algorithm proposed is suitable for implementation on a parallel computation model. On the EREW PRAM model, our algorithm runs either in logn time using O(n) processors for the unsorted case or in O(logn) time using O(n/logn) processors for the sorted case. The proposed algorithms for both cases are of optimal speed-up. If the dominator matrix is required, it can be computed in O(n2) time on a sequential machine, or in O(logn) time on an EREW PRAM model using O(n2/ logn) processors.
Keywords: interval graphs, density sequence, dominators, parallel algorithms, EREW PRAM, optimal speed-up
Received November 21, 1995; revised October 8, 1996.
Communicated by Shing-Tsaan Huang.
*This work was supported by the National Science Council, Republic of China, under contract No.: NSC-84-2213-E-011-015.