(3.235.25.169) 您好!臺灣時間:2021/04/18 03:39
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

我願授權國圖
: 
twitterline
研究生:尹宗耀
研究生(外文):Zong-Yau Yin
論文名稱:找尋有向圖上所有延伸樹的演算法
論文名稱(外文):An Algorithm for Enumerating All Spanning Trees of a Directed Graph
指導教授:王炳豐
指導教授(外文):Biing-Feng Wang
學位類別:碩士
校院名稱:國立清華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:中文
論文頁數:25
中文關鍵詞:延伸樹有向圖列舉演算法
外文關鍵詞:spanning treedirected graphenumerationgraphsalgorithms
相關次數:
  • 被引用被引用:0
  • 點閱點閱:142
  • 評分評分:系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔系統版面圖檔
  • 下載下載:0
  • 收藏至我的研究室書目清單書目收藏:0
令 G = (V, E) 為一無向圖 (undirected graph) 或有向圖 (directed graph)。令 n = |V| 且 m = |E|。將 G 的所有延伸樹 (spanning tree) 列舉 (enumerate) 出來是一個相當古老的問題,從 1968 年開始,就有 Gabow和Tarjan 等大師開始對這個問題進行研究。
當 G 為無向圖時,在 1997 年的時候,Shioura、Tamura 和 Uno 就已提出了將 G 的所有延伸樹列舉出來的最佳化 (optimal) 演算法。這裡所謂的最佳化指的是這個演算法的時間複雜度 (time complexity),執行時的空間複雜度 (space complexity),以及輸出所需要用到的空間複雜度 (output size complexity) 都已經是最好的。
當 G 為有向圖時,這個問題一直都沒有最佳化的演算法。在有向圖中,延伸樹的定義為:在一個延伸樹中,其根 (root) 到每一個其它的vertex 都有一條唯一的路徑 (path)。在 2000 年時,Kapoor 和 Ramesh 提出了一個輸出空間複雜度是 O(N + n^2) 的演算法,這樣的輸出空間複雜度是目前最好的;但是這一個演算法在執行中卻須要用到 O(n^2) 的空間。N 為 G 中所有延伸樹的個數。
在這篇論文中,我們提出了一個將有向圖中所有延伸樹都列舉出來的演算法,這一個演算法使用了 Kapoor 和 Ramesh 所提出的 “edge-exchange” 技術,只要把目前所列舉到的延伸樹換一根 edge 就可以產生出另一個新的延伸樹。這一個演算法的輸出空間複雜度跟Kapoor 和 Ramesh的演算法一樣,都是O(N + n^2)。在空間複雜度上,我們所提出的方法是最佳的 O(n + m)。不過在時間複雜度上,我們的方法和 Kapoor 與 Ramesh 的方法相比,稍微慢一點。我們的是 O(Nnlogn + n^2 + nm);Kapoor 與 Ramesh 的是 O(Nn + n^3)。

Let G = (V, E) be a directed graph with vertex set V and edge set E. A directed spanning tree of G rooted at a vertex r is a spanning tree of G having a unique path from r to every other vertex. In this thesis, by using Kapoor and Ramesh’s [8] “edge-exchange” technique, we propose an O(Nnlogn + n^2 + nm) time algorithm for enumerating all spanning trees of a directed graph. The output size of our algorithm is O(N + n^2) that is the same as Kapoor and Ramesh’s algorithm in [8]. Furthermore, although our algorithm is slightly slower than Kapoor and Ramesh’s, the space complexity of our algorithm is O(n + m), which is optimal.

Content.....................................................i
List of Tables.............................................ii
List of Figures...........................................iii
Chapter 1 Introduction......................................1
Chapter 2 Preliminaries.....................................4
2.1 Definitions and Notations............................4
2.2 Algorithm Outline....................................5
2.3 Computation Tree.....................................7
Chapter 3 Kapoor and Ramesh’s Algorithm...................10
Chapter 4 A New Implementation.............................13
4.1 A New Implementation................................13
4.2 Complexity..........................................20
Chapter 5 Concluding Remarks...............................23
References.................................................24

[1] D. Avis and K. Fukuda, “ A Basis Enumeration Algorithm
for Linear Systems with Geometric Applications,” Applied
Mathematics Letters, vol. 4, pp. 39-42, 1991.
[2] D. Avis and K. Fukuda, “ Reverse Search for Enumeration,”
Discrete Applied Mathematics, vol. 65, pp.21-46, 1996.
[3] J. P. Char, “ Generation of Trees, 2 Trees and Storage of
Master Forests,” IEEE Transactions on Circuit Theory, vol.
15, pp. 128-138, 1968.
[4] H. N. Gabow, “ Two Algorithms for Generating Weighted
Spanning Trees in Order,” SIAM Journal on Computing, vol.
6, pp. 139-150, 1977.
[5] S. L. Hakimi and D. G. Green, “ Generation and Realization
of Trees and k-Trees,” IEEE Transactions on Circuit
Theory, vol. 11, pp. 247-255, 1964.
[6] R. Jayakumar, K. Thulasiraman, and M. N. S. Swamy, “
Complexity of Computation of a Spanning Tree Enumerating
Algorithm,” IEEE Transactions on Circuits and Systems,
vol. 31, pp. 853-860, 1984.
[7] S. Kapoor and H. Ramesh, “ Algorithms for Generating All
Spanning Trees of Undirected and Weighted Graph,” SIAM
Journal on Computing, vol. 24, pp. 247-265, 1995.
[8] S. Kapoor and H. Ramesh, “ An Algorithm for Enumerating
All Spanning Trees of a Directed Graph,“ Algorithmica,
vol. 27, pp. 120-130, 2000.
[9] T. Matsui, “ An Algorithm for Finding All the Spanning
Trees in Undirected Graph,” Research Report, Department of
Mathematical Engineering and Information Physics,
University of Tokyo, Tokyo, 1993.
[10] W. Mayeda, Graph Theory, Wiley, New York, 1972.
[11] W. Mayeda and S. Seshu, “ Generation of Trees without
Duplications,” IEEE Transactions on Circuit Theory, vol.
12, pp. 181-185, 1965.
[12] G. J. Minty, “ A Simple Algorithm for Listing All the
Trees of a graph,” IEEE Transactions on Circuit and
Systems, vol. 12, p.120, 1965.
[13] E. W. Myers and H. N. Gabow, “ Finding All Spanning Trees
of Directed and Undirected Graph,” SIAM Journal on
Computing, vol. 7, pp. 280-287, 1978.
[14] R. C. Read and R. E. Tarjan, “ Bounds on Backtrack
Algorithms for Listing Cycles, Paths, and Spanning
Trees,” Networks, vol. 5, pp. 237-252, 1975.
[15] S. Shinoda, “ Finding All Possible Directed Trees of a
Directed Graph,” Electronics and Communications in Japan,
vol. 51-A, pp. 45-47, 1968.
[16] A. Shioura and A. Tamura, “ Efficient Scanning All
Spanning Trees of an Undirected Graph,” Journal of the
Operations Research Society of Japan, vol. 38, pp. 331-
344, 1995.
[17] A. Shioura, A. Tamura, and T. Uno, “ An Optimal Algorithm
for Scanning All Spanning Trees of Undirected Graphs,”
SIAM Journal on Computing, vol. 26, pp. 678-692, 1997.
[18] D. D. Sleator and R. E. Tarjan, “ A Data Structure for
Dynamic Trees,” Journal of Computer and System Sciences,
vol. 26, pp. 362-391, 1983.
[19] R. E. Tarjan, “ Depth-First Search and Linear Graph
Algorithms,” SIAM Journal on Computing, vol. 1, pp.146-
160, 1972.
[20] T. Uno, “ A New Approach for Speeding Up Enumeration
Algorithms,” ISSAC 1998, Lecture Notes in Computer
Science, vol. 1533, Springer-Verlag, pp. 287-296.
[21] T. Uno, “ A New Approach for Speeding Up Enumeration
Algorithm and Its Application for Matroid Bases,” COCOON
1999, Lecture Notes in Computer Science, vol. 1627,
Springer-Verlag, pp. 349-359.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
系統版面圖檔 系統版面圖檔