JISE


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


Journal of Information Science and Engineering, Vol. 13 No. 4, pp. 615-629


Computing Dominators on Interval Graphs


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

  Retrieve PDF document (JISE_199704_06.pdf)