Constant-Time Algorithms for Dominating Problem on Circular-Arc Graphs

Author: Shun-Shii Lin, Ching-Fung Lee(Department of Information and Computer Education, National Taiwan Normal University)

Vol.&No.：Vol. 44, No. 1
Date：April 1999
Pages：31-42
DOI：10.6301/JNTNU.1999.44(1).03

Abstract：

The objective of this paper is to solve the dominating problem on circular-arc graphs in O(l) time. This problem has not been solved in O(l) time before, even on the ideal PRAM model. In this paper, we take advantage of the characteristics of the PARES (processor arrays with reconfigurable bus systems), which can connect the inner buses in O(l) time. We use O(n2) processors in the study. By combining the characteristics of PARES and improving the methods of [14][15], we are able to derive constant-time algorithms for this problem.

Keywords：Circular-arc graphs, Dominating problem, PARES (processor arrays with reconfigurable bus systems)

《Full Text》