查詢結果分析
來源資料
相關文獻
- An Algorithm for Finding a Cycle in Planar Graph Subpartitioning
- Generalized Gray Codes with Applications
- Distributed Broadcasting Algorithms in Rotator Graphs
- Fractal Image Coding Using Projection-Based Classification and Variable Shape Matching
- 以類神經網絡模式分析颱風降雨與半分布並聯式水庫概念模式模擬颱洪歷線之串聯應用
- 線性軸幅路網接駁系統最適整合區位、路線與排班模式之研究
- 都市計畫草圖替選方案分析模式之實例研究
- MUSCL Type Algorithm for Acoustic Wave Equations in Heterogeneous Media
- 運用類神經網路於股價指數之套利--以日經225指數為例
- Genetic Algorithm Approach for Designing Fir Hilbert Transformers and Differentiators
頁籤選單縮合
題 名 | An Algorithm for Finding a Cycle in Planar Graph Subpartitioning=找出環形路徑完成平面圖分割之演算法 |
---|---|
作 者 | 邱創乾; | 書刊名 | 逢甲學報 |
卷 期 | 28 1995.11[民84.11] |
頁 次 | 頁495-510 |
分類號 | 448.945 |
關鍵詞 | 環形路徑; 平面圖分割; 演算法; |
語 文 | 英文(English) |
中文摘要 | 在本論文�堙A我們提出新的演算法用以找出一個環形路徑來完成平面圖內的圖點 分割。雖然平面圖上的點分割理論之證明及推演最早在 Lipton 與 Tarjan 的文章內已被提 出,但若要將他們的結果實際運用在大型圖形的點分割上,是有其執行上的困難,而其中最 大的瓶頸即在找出一個合法的環形路徑,以完成整個平面圖的分割。我們提出的演算法,不 僅方法簡單易實現, 且能實際運用於大型圖形的點分割上, 它的精簡內容包括將原先在 Lipton 與 Tarjan 的方法內要把平面圖上各面 (face) 三角化的步省驟省略或最少化, 以 及用一種極簡單的方法決定哪些圖點須被考慮嵌在環形路徑之內,哪些應置於環形路徑之外 。我們以一種極易理解且容易程式化的方法解說這個演算法的過程,並於文中列舉一個完整 的例子說明它的作法。 |
英文摘要 | In this paper, an algorithm for finding a cycle to complete the vertex partitioning of planar graphs is described. Although a theoretical algorithm of this type has been known since the pioneering work of Lipton and Tarjan (L&T) on their separator theorem, the proposed algorithm is much simpler. It is amenable to practical implementation and is good for partitioning a large graph in real time. The simplifications of the algorithm with respect to L&T include the elimination or minimization of the need for triangulation, and a simple rule to determine which vertices should be considered inside of the cycle and which vertices outside. The algorithm is described in an easily understood, easily programmable manner. |
本系統中英文摘要資訊取自各篇刊載內容。