呂學一Lu, Hsueh-I臺灣大學:資訊工程學研究所劉宗灝Liu, Tsung-HaoTsung-HaoLiu2010-05-182018-07-052010-05-182018-07-052008U0001-1607200813385900http://ntur.lib.ntu.edu.tw//handle/246246/183657本論文提出第一個在加權外部平面圖(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.Acknowledgements ihinese Abstract iinglish Abstract iiiontents ivist of Figures vi Introduction 1 Basics 5.1 Lex short cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Tight cycles and loose cycles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 The Algorithm 10.1 The compact representation for tight cycles . . . . . . . . . . . . . . . . . . . . 10.2 The compact representation for loose cycles . . . . . . . . . . . . . . . . . . . . 11.3 Proving Theorem 1.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 Concluding Remarks 14ibliography 15application/pdf296753 bytesapplication/pdfen-US迴圈基底外部平面圖資料結構cycle basisouterplanardata structurethesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/183657/1/ntu-97-R95922122-1.pdf