環弧圖上支配問題之常數時間演算法

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

在本篇論文中，我們利用可重組態匯流排之處理器陣列（PARBS, processor arrays with reconfigurable bus systems）具有在O(1）時間中動態連結內部不同的匯排流之特性，在常數時間內解決在環弧圖(circular-arc graphs）上的支配問題(the dominating problem）。關於環弧圖上的支配問題，以前尚未有人在常數時間內解決，即使是在理想的PRAM模型上也是如此，在本論文中，我們改良Yu[14][15]中提到的相關演算法，然後再自行發展出一套理論，並且將之推廣至可重組態匯流排之處理器陣列模型上。我們以O(n2）個處理器之可重組態匯流排處理器陣列作為主要的計算模型，使得我們能在常數時間內解決支配問題。

The objective of this paper is to solve the dominating problem on circular-arc graphs in O(1） time. This problem has not been solved in O(1） 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(1） time. We use O(n）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.