臺灣博碩士論文加值系統

對於一個給定的圖形，找出其最佳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.