Please use this identifier to cite or link to this item:
Title: Constant-Time Algorithms for Dominating Problem on Circular-Arc Graphs
Other Titles: 環弧圖上支配問題之常數時間演算法
Authors: 林順喜
Shun -Shii Lin and Ching-Fung Lee
Issue Date: Oct-1999
Publisher: 國立臺灣師範大學研究發展處
Office of Research and Development
Abstract: 在本篇論文中,我們利用可重組態匯流排之處理器陣列(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(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.
Other Identifiers: 9B52DE23-DA3F-D368-D506-455D14C72914
Appears in Collections:師大學報:數理與科技類

Files in This Item:
File SizeFormat 
ntnulib_ja_L0803_4401_031.pdf455.78 kBAdobe PDFView/Open

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.