# 臺灣博碩士論文加值系統

(44.220.50.41) 您好！臺灣時間：2024/08/08 15:52

:::

### 詳目顯示

:

• 被引用:0
• 點閱:312
• 評分:
• 下載:26
• 書目收藏:0
 對於一個給定的圖形，找出其最佳vertex ranking 和建立該圖的最小高度消去樹一直是令人關注的計算問題。從一般的圖形中找出其對應的最小高度消去樹已經被証明為NP-hard 問題。一個最佳化vertex ranking 無法提供足夠的資訊去建立其最小高度消去樹。然而，最佳化vertex ranking 卻可以直接地由最小高度消去樹來獲得。對於樹，最佳化vertex ranking 問題的演算法已經可以在線性時間內完成；而要建立樹的最小高度消去樹，其演算法卻仍然需要O(nlogn) 的時間。在這篇論文裡，我們提出一個線性時間的演算法用來建立樹的最小高度消去樹。
 Given a graph, finding an optimal vertex ranking and constructing minimum heightelimination trees are interesting computational problems. The problem of finding theminimum 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 constructan elimination tree of minimum height. On the other hand, an optimal vertex rankingcan readily be found directly from an elimination tree of minimum height.On trees, the optimal vertex ranking problem already has a linear-time algorithmin the literature. However, there is no Linear-time algorithm for the problem offinding minimum height elimination trees. A naive algorithm for this problem requiresO(n log n) time.In this thesis, we propose a linear-time algorithm for constructing a minimumheight elimination tree of a tree.
 Abstract iContents iiList of Figures iiiList of Tables iv1 Introduction 12 Preliminaries 63 Main Result 94 Concluding Remarks 15Bibliography 16
 [1] H.L. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. M¨uller, andZs. 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, Approximatingtreewidth, 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 permutationand other graphs, Proc. of the 11th Annual Symposium on TheoreticalAspects 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 symmetriclinear 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, InformationProcessing 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-freegraphs, 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 AnnualIEEE Symposium on Foundations of Computer Science, 1980, pp. 270-281.[10] J.W.H. Liu, The role of elimination trees in sparse factorization, SIAM Journalof Matrix Analysis and Applications, 11(1990), pp. 134-172.[11] P.M. Lewis, R.E. Stearns, and J. Hartmanis, Memory bounds for recognition ofcontext-free and context-sensitive languages, Proc. 6th Annual Symposium onSwitching 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 ProcessingLetters 33(1989/1990), pp. 91-96.[15] P. Sche²er, Node ranking and searching on graphs (Abstract), in 3rd TwenteWorkshop on Graphs and Combinatorial Optimization, U. Faigle, and C. Hoede,eds., Memorandum No. 1132, Faculty of Applied Mathematics, University ofTwente, The Netherlands, 1993.[16] A. Sen, H. Deng, and S. Guha, On a graph partition problem with applicationto 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 inpolynomial time, Proc. of the 4th Annual ACM-SIAM Symposium on DiscreteAlgorithms, 1993, pp. 138-144.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 無相關期刊

 1 一個有效率的演算法解決原始似星圖上的區間圖完成問題 2 應用於MPEG-4視訊形狀編碼資訊之時間域與空間域錯誤隱藏演算法 3 以XML為基礎之跨企業工作流樣版，程序模式化與商務活動管理 4 使用資料隱藏的影像竄改回覆技術 5 雙層式軟體程序描述語言 6 電探針在電漿量測系統中的設計與模擬 7 多代理人階層式合作策略之研究與比較分析─以RoboCupRescue為例 8 使用整合DTD之XML資料庫查詢 9 針對可移動資料源提供位置關聯式擷取之行動代理人與動態資料管理策略 10 植基於浮水印的錯誤隱藏技術 11 應用FUDChains進行迴圈中常數傳遞之分析 12 多角度人臉之二階段辨識 13 植基於小波技術之多頻帶偵測浮水印方法 14 近似輪廓邊線的萃取 15 一個一致的方法解決雙分排列圖上樹寬和最少填入邊問題

 簡易查詢 | 進階查詢 | 熱門排行 | 我的研究室