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