期刊目錄列表 - 44卷第1.2期(1999) - 【數理與科技類】44(1) 四月刊
Directory
環弧圖上支配問題之常數時間演算法
作者:林順喜、李青芳(國立臺灣師範大學資訊教育研究所)
卷期：44卷第1期
日期：1999年4月
頁碼：31-42
DOI：10.6301/JNTNU.1999.44(1).03
摘要：
在本篇論文中，我們利用可重組態匯流排之處理器陣列（PARBS, processor arrays with reconfigurable bus systems）具有在O(1)時間中動態連結內部不同的匯排流之特性，在常數時間內解決在環弧圖(circular-arc graphs)上的支配問題(the dominating problem)。關於環弧圖上的支配問題，以前尚未有人在常數時間內解決，即使是在理想的PRAM模型上也是如此，在本論文中，我們改良Yu[14][15]中提到的相關演算法，然後再自行發展出一套理論，並且將之推廣至可重組態匯流排之處理器陣列模型上。我們以O(n2)個處理器之可重組態匯流排處理器陣列作為主要的計算模型，使得我們能在常數時間內解決支配問題。
關鍵詞：環弧圖、支配問題、可重組態匯流排之處理器陣列
《詳全文》
Journal directory listing - Volume 44 (1999) - Mathematics, Science & Technology【44(1)】April
Directory
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)