加權外部平面圖之最小迴圈基底

Minimum Cycle Bases of Weighted Outerplanar Graphs

劉宗灝(Tsung-Hao Liu)

指導教授 ： 呂學一

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2008年)

https://doi.org/10.6342/NTU.2008.00893

摘要

本論文提出第一個在加權外部平面圖(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.

並列關鍵字

cycle basis ； outerplanar ； data structure

參考文獻

[1] F. Berger, P. Gritzmann, and S. de Vries. Minimum cycle bases for network graphs. Algorithmica, 40:51–62, 2004.

[2] D. Coppersmith and S. Winograd. Matrix multiplication via arithmetic progressions. Journal of Symbolic Computation, 9(3):251–280, 1990.

[3] J. C. de Pina. Applications of Shortest Path Methods. PhD thesis, University of Amsterdam, Netherlands, 1995.

[4] G. N. Frederickson and R. Janardan. Designing networks with compact routing tables. Algorithmica, 3:171–190, 1988.

[5] A. Golynski and J. D. Horton. A polynomial time algorithm to find the minimum cycle basis of a regular matroid. In Proceedings of the 8th Scandinavian Workshop on Algorithm Theory, pages 200–209, 2002.