請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37439
標題: | 加權外部平面圖之最小迴圈基底 Minimum Cycle Bases of Weighted Outerplanar Graphs |
作者: | Tsung-Hao Liu 劉宗灝 |
指導教授: | 呂學一(Hsueh-I Lu) |
關鍵字: | 迴圈基底,外部平面圖,資料結構, cycle basis,outerplanar,data structure, |
出版年 : | 2008 |
學位: | 碩士 |
摘要: | 本論文提出第一個在加權外部平面圖(weighted outerplanar graph) 上計算最小迴圈基底(minimum cycle basis) 的最佳演算法。更精確地說, 對於任何一個擁有n 個點的加權外部平面圖G, 本論文提出一個O(n) 時間的演算法, 對G 的一組最小迴圈基底C 計算出一個O(n) 空間的精簡表示 (compact representation) Z(C) 。此外, C 中的每一個迴圈, 可在每條邊花費O(1) 時間的情況下由 Z(C) 得知。 We give the first known optimal algorithm that computes a minimum cycle basis for any weighted outerplanar graph. Specifically, for any n-node edge-weighted outerplanar graph G, we give an O(n)-time algorithm to obtain an O(n)-space compact representation Z(C) for a minimum cycle basis C of G. Each cycle in C can be computed from Z(C) in O(1) time per edge. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/37439 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-97-1.pdf 目前未授權公開取用 | 289.8 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。