Constant-Time Algorithms for the Minimum Circle-Cover Problem on Circular-Arc Graphs

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

Abstract：

In this paper, we present an O(l) time algorithm to solve the minimum circle-cover problem defined on circular-arc graphs based on the processor arrays with a reconfig-urable bus system ( abbreviated to PARBS ) which consist of a processor array and a reconfigurable bus system. This problem has not been solved in O(l) time before, even on the idealistic CRCW PRAM model. In order to solve this problem with constant time complexity, we first introduce the concept of iterative PARBS which is similar to the FOR-loop construct in sequential programming languages. Then we develop an O(l)-time algorithm to compute the level of each node of a forest. Based on those re-sults, we are able to explore constant-time parallel algorithms on PARBS for the mini-mum circle-cover of a circular-arc graph. The following new results are derived in this study.

Keywords：circular-arc graph, minimum circle-cover problem, parallel processing, processor array, reconfigurable bus system

《Full Text》