Please use this identifier to cite or link to this item:
Title: Constant-Time Algorithms for the Minimum Circle-Cover Problem on Circular-Arc Graphs
Other Titles: 環弧圖上最小覆蓋圖問題的常數時間演算法
Authors: 林順喜
Issue Date: Jun-1996
Publisher: 國立臺灣師範大學研究發展處
Office of Research and Development
Abstract: 在本論文中,我們提出○(1)時間的演算法,以解決環弧圖上最小履蓋圓的問題。我們的演算法乃使用可重組態匯流排系統之處理器陣列(簡稱PARBS),它含有一處理器陣列以及一可重組態匯流排系統。此問題以前從沒有在○(1)時間內被解決過,即使是在極理想的CRCW PRAM計算模型上。為了能以常數時間之複雜度解決此問題,我們先提出 iterative-PARBS的設計觀念,類似循序程式語言中的FOR迴圈,接著我們設計出一套常數時間的平行演算法,用來計算-forest中每一節點的階層。根據這些結果,我們得以在PARBS 上發展出常數時間的平行演算法,以解決環弧圖上最小覆蓋圓的問題。以下是我們所得到的新結果:(1)一具有n個節點的forest中每一節點的階層,可在一含有○(n���瞴^個處理器之PARBS 上,以○(1)時間求出,此處ε>0。(2)一環弧圖上之最小覆蓋圓,可在一含有○(n���瞴^個處理器之PARBS上,以○(1)時 間求出,此處ε>0。
In this paper, we present an ○(1) time algorithm to solve the minimum circle-cover problem defined on circular-arc graphis based on the processor arrays with a reconfigurable bus system (abbreviated to PARBS) which consist of a processor array and a reconfigurable bus system. This problem has not been solved in ○(1) 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 ○(1)-time algorithm to compute the level of each node of a forest. Based on those results, we are able to explore constant-time parallel algorithms on PARBS for the minimum circle-cover of a circular-arc graph. The following new results are derived in this study: (1)The level of each node of a forest with n nodes can be computed in ○(1) time on a PARBS with ○(n����) processors for any "fixed" ε>0. (2)The minimum circle-cover of a circular-arc graph can be derived in ○(1) time on a PARBS with ○(n����) processors for any "fixed" ε>0.
Other Identifiers: A74D3A73-C355-3A2D-098B-36DEC38713FE
Appears in Collections:師大學報

Files in This Item:
File SizeFormat 
ntnulib_ja_L0801_0041_133.pdf1.05 MBAdobe PDFView/Open

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