跳到主要內容

臺灣博碩士論文加值系統

(3.239.4.127) 您好!臺灣時間:2022/08/16 03:18
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:施崇暉
研究生(外文):Chong-Hui Shi
論文名稱:一個線性時間演算法建造樹的最小高度消去樹
論文名稱(外文):A Linear-Time Algorithm for Constructinga Minimum Height Elimination Tree of a Tree
指導教授:彭勝龍彭勝龍引用關係
指導教授(外文):Sheng-Lung Peng
學位類別:碩士
校院名稱:國立東華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:18
中文關鍵詞:最小高度消去樹
外文關鍵詞:optimal vertex rankingminimum height elimination tree
相關次數:
  • 被引用被引用:0
  • 點閱點閱:249
  • 評分評分:
  • 下載下載:22
  • 收藏至我的研究室書目清單書目收藏:0
對於一個給定的圖形,找出其最佳vertex ranking 和建立該圖的
最小高度消去樹一直是令人關注的計算問題。從一般的圖形中找出其
對應的最小高度消去樹已經被証明為NP-hard 問題。一個最佳化
vertex ranking 無法提供足夠的資訊去建立其最小高度消去樹。然
而,最佳化vertex ranking 卻可以直接地由最小高度消去樹來獲得。
對於樹,最佳化vertex ranking 問題的演算法已經可以在線性時
間內完成;而要建立樹的最小高度消去樹,其演算法卻仍然需要
O(nlogn) 的時間。
在這篇論文裡,我們提出一個線性時間的演算法用來建立樹的最
小高度消去樹。
Given a graph, finding an optimal vertex ranking and constructing minimum height
elimination trees are interesting computational problems. The problem of finding the
minimum height elimination trees has been shown to be NP-hard on general graphs.
An optimal vertex ranking does not by itself provide enough information to construct
an elimination tree of minimum height. On the other hand, an optimal vertex ranking
can readily be found directly from an elimination tree of minimum height.
On trees, the optimal vertex ranking problem already has a linear-time algorithm
in the literature. However, there is no Linear-time algorithm for the problem of
finding minimum height elimination trees. A naive algorithm for this problem requires
O(n log n) time.
In this thesis, we propose a linear-time algorithm for constructing a minimum
height elimination tree of a tree.
Abstract i
Contents ii
List of Figures iii
List of Tables iv
1 Introduction 1
2 Preliminaries 6
3 Main Result 9
4 Concluding Remarks 15
Bibliography 16
[1] H.L. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. M¨uller, and
Zs. Tuza, Rankings of graphs, Proc. of the International Workshop on Graph-
Theoretic Concepts in Computer Science, Lecture Notes in Computer Science,
Springer-Verlay, 903(1994), pp. 292-304.
[2] H.L. Bodlaender, J.R. Gilbert, H. Hafsteinsson, and T. Kloks, Approximating
treewidth, pathwidth, frontsize and shortest elimination tree, Journal of Algorithms,
18(1995), pp. 238-255.
[3] J.S. Deogun, T. Kloks, D. Kratsch, and H. M¨aller, On vertex ranking for permutation
and other graphs, Proc. of the 11th Annual Symposium on Theoretical
Aspects of Computer Science, Lecture Notes in Computer Science, Spring-Verlag,
775(1994), pp. 747-758.
[4] I.S. Du®, and J.K. Reid, The multifrontal solution of indefinite sparse symmetric
linear equations, ACM Transactions on Mathematical Software, 9(1983), pp.
302-325.
[5] A.V. Iyer, H.D. Ratli®, and G. Vijayan, Parallel assembly of modular products
- an analysis, Technical Report 88-06, Georgia Institute of Technology, 1988.
[6] A.V. Iyer, H.D. Ratli®, and G. Vijayan, Optimal node ranking of trees, Information
Processing Letters, 28(1988), pp. 225-229.
[7] M. Katchalski, W. McCuaig, and S. Seager, Ordered colourings, Discrete Mathematics,
142(1995), pp. 141-154.
[8] T. Kloks, H. M¨aller, and C.K. Wong, Vertex ranking of asteroidal triple-free
graphs, Proc. of the 7th International Symposium on Algorithms and Computation
(ISAAC’96), Lecture Notes in Computer Science, Springer-Verlag,
1178(1996), pp. 174-182.
[9] C.E. Leiserson, Area e±cient graph layouts for VLSI, Proc. of the 21th Annual
IEEE Symposium on Foundations of Computer Science, 1980, pp. 270-281.
[10] J.W.H. Liu, The role of elimination trees in sparse factorization, SIAM Journal
of Matrix Analysis and Applications, 11(1990), pp. 134-172.
[11] P.M. Lewis, R.E. Stearns, and J. Hartmanis, Memory bounds for recognition of
context-free and context-sensitive languages, Proc. 6th Annual Symposium on
Switching Theory and Logic Design, 1965, pp. 191-202.
[12] J. Nevins, and D. Whitney, eds., Concurrent Design of Products and Processes,
McGraw-Hill, 1989.
[13] A. Pothen, The complexity of optimal elimination trees, Technical Report CS-
88-13, Pennsylvania State University, USA, 1988.
[14] A.A. Sch¨a®er, Optimal node ranking of trees in linear time, Information Processing
Letters 33(1989/1990), pp. 91-96.
[15] P. Sche²er, Node ranking and searching on graphs (Abstract), in 3rd Twente
Workshop on Graphs and Combinatorial Optimization, U. Faigle, and C. Hoede,
eds., Memorandum No. 1132, Faculty of Applied Mathematics, University of
Twente, The Netherlands, 1993.
[16] A. Sen, H. Deng, and S. Guha, On a graph partition problem with application
to VLSI layout, Information Processing Letters, 43(1992), pp. 87-94.
[17] P. de la Torre, R. Greenlaw, and T.M. Przytycka, Optimal tree ranking is in NC,
Parallel Processing Letters, 2(1992), pp. 31-41.
[18] P. de la Torre, R. Greenlaw, and A.A. Sch¨a®er, Optimal ranking of trees in
polynomial time, Proc. of the 4th Annual ACM-SIAM Symposium on Discrete
Algorithms, 1993, pp. 138-144.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top