請用此 Handle URI 來引用此文件: http://rportal.lib.ntnu.edu.tw:80/handle/20.500.12235/17518
標題: Constant-Time Algorithms for the Minimum Circle-Cover Problem on Circular-Arc Graphs
其他標題: 環弧圖上最小覆蓋圖問題的常數時間演算法
作者: 林順喜
公開日期: 六月-1996
出版社: 國立臺灣師範大學研究發展處
Office of Research and Development
摘要: 在本論文中,我們提出○(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.
URI: http://rportal.lib.ntnu.edu.tw/handle/20.500.12235/17518
其他識別: A74D3A73-C355-3A2D-098B-36DEC38713FE
顯示於類別:師大學報

文件中的檔案:
檔案 大小格式 
ntnulib_ja_L0801_0041_133.pdf1.05 MBAdobe PDF檢視/開啟


在 DSpace 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。