環弧圖上最小覆蓋圓問題的常數時間演算法 作者:林順喜(國立臺灣師範大學資訊教育研究所)

摘要：

在本論文中，我們提出O(1) 時間的演算法，以解決環弧圖上最小覆蓋圓的問題。我們的演算法乃使用可重組態匯流排系統之處理器陣列（簡稱PARBS），它含有一處理器陣列以及一可重組態匯流排系統。此問題以前從沒有在O(1) 時間內被解決過，即使是在極理想的CRCW PRAM計算模型上。為了能以常數時間之複雜度解決此問題，我們先提出iterative-PARBS的設計觀念，類似循序程式語言中的FOR迴圈。接著我們設計出一套常數時間的平行演算法，用來計算一forest中每一節點的階層。根據這些結果，我們得以在PARBS上發展出常數時間的平行演算法，以解決環弧圖上最小覆蓋圓的問題。以下是我們所得到的新結果：
(1)一具有n個節點的forest中每一節點的階層，可在一含有O(n^2+e ) 個處理器之PARBS上，以O(1)時間求出，此處ε >0。
(2)一環弧圖上之最小覆蓋圓，可在一含有O(n^2+e) 個處理器之PARBS上，以O(1) 時間求出，此處ε >0。

關鍵詞：環弧圖、最小覆蓋圓問題、平行處理、處理器陣列、可重組態匯流排系統

《詳全文》

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