查詢結果分析
相關文獻
- Constant-Time Algorithms for the Minimum Circle-Cover Problem on Circular-Arc Graphs
- Constant-Time Algorithms for Dominating Problem on Circular-Arc Graphs
- Constant-Time Algorithms for the Area and Perimeter of Image Components on Processor Arrays with Reconfigurable Bus Systems
- 個人電腦影像處理技術應用於即時車輛面式偵測
- 模糊性拜占庭協議[Byzantine Agreement]初探
- PASS認知歷程模式在國小閱讀障礙兒童認知歷程分析上之應用
- 摺疊式超立方體上完全二元樹嵌入的性質
- 改良式以分散數學為基礎之反離散餘弦函數轉換
- 在超立方體平行計算機上利用8×8分割之碎形影像壓縮的平行化計算之研究
- Java Engine: The Java Processors to Enhance Execution Performance
頁籤選單縮合
題 名 | Constant-Time Algorithms for the Minimum Circle-Cover Problem on Circular-Arc Graphs=環弧圖上最小覆蓋圖問題的常數時間演算法 |
---|---|
作 者 | 林順喜; | 書刊名 | 師大學報 |
卷 期 | 41 1996.06[民85.06] |
頁 次 | 頁133-176 |
分類號 | 310.153 |
關鍵詞 | 環弧圖; 最小覆蓋圓問題; 平行處理; 處理器陣列; 可重組態匯流排系統; Circular-arc graph; Minimum circle-cover problem; Parallel processing; Processor array; Reconfigurable bus system; |
語 文 | 英文(English) |
中文摘要 | 在本論文中,我們提出○(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. |
本系統中英文摘要資訊取自各篇刊載內容。