跳到主要內容

臺灣博碩士論文加值系統

(44.201.97.0) 您好!臺灣時間:2024/04/14 04:53
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:鄭競元
研究生(外文):Ching-Yuan Cheng
論文名稱:一個有效率的演算法解決二分排列子圖上點分級的問題
論文名稱(外文):An Efficient Algorithm for the Vertex Ranking Problem on Proper Bipartite Permutation Graphs
指導教授:彭勝龍彭勝龍引用關係
指導教授(外文):Sheng-lung Peng
學位類別:碩士
校院名稱:國立東華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2003
畢業學年度:91
語文別:英文
論文頁數:33
中文關鍵詞:二分排列子圖點分級
外文關鍵詞:vertex rankingproper bipartite permutation graphs
相關次數:
  • 被引用被引用:0
  • 點閱點閱:135
  • 評分評分:
  • 下載下載:2
  • 收藏至我的研究室書目清單書目收藏:1


對於一個給定的圖形,點著色的問題是使用最少顏色對每個點做
塗色,使得兩個相鄰的點被塗不同的顏色。而點分級的問題是一個限
制的點著色的問題。一個圖形的點分級是對此圖的每一個點做著色
(分級),由數字取代顏色後,假設有兩個不同的點擁有相同的數字,
則這兩點之間的每一條路徑,必定存在一個擁有更大數字的點。點分
級的問題是去尋找一個給定圖形的點分級,使得最大的數字盡可能越
小越好。在本篇論文裡面,我們提出一個O(n3)時間的演算法去解決
二分排列子圖上點分級的問題,這裡的n是指圖形上點的個數。



The vertex coloring problem is to color the vertices of a given graph with the minimum number of colors such that no two adjacent vertices are assigned the same color. The vertex ranking problem is a restriction of the vertex coloring problem. By associating each color with a positive integer, a vertex ranking of a graph G is a coloring (ranking) of the vertices of G such that if two distinct vertices have the same color number, then there exists a vertex with a higher color number for every path of the two vertices. The vertex ranking problem is to find a vertex ranking of a given graph G such that the largest rank assigned is as small as possible. In this thesis, we present an O(n3)-time algorithm for the vertex ranking problem on proper bipartite permutation graphs where n is the number of vertices of the input graph.



Abstract i
Contents ii
List of Figures iii
List of Tables v
1 Introduction 1
2 Preliminaries 6
2.1 Definitions about related graph classes . . . . . . . . . . . . . . . . . 6
2.2 Bicliques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3 Main Results 13
3.1 Vertex ranking and minimum height elimination tree . . . . . . . . . 13
3.2 An O(n3)-time Algorithm . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Concluding Remarks 29
Bibliography 30



[1] N. Abbas, L.K. Stewart, Biconvex graphs: ordering and algorithms, Discrete
Applied Mathematics, 103(2000), pp. 1-19.
[2] H.L. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Muller, and
Zs. Tuza, Rankings of graphs, SIAM J. Discrete Math, 11(1998), pp. 168-181.
[3] 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.
[4] J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Muller, On the vertex ranking
problem for trapezoid, circular-arc and other graphs, Discrete Applied Mathematics,
98(1999), pp. 39-63.
[5] J.S. Deogun, T. Kloks, D. Kratsch, and H. Maller, 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.
[6] I.S. Duff, and J.K. Reid, The multifrontal solution of indefinite sparse symmetric
linear equations, ACM Transactions on Mathematical Software, 9(1983), pp. 302-325.
[7] F. Glover, Maximum matching in a biconvex bipartite graph, Naval Res. Logist. Quart, 14(1967), pp. 313-316.
[8] M.C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980.
[9] S.Y. Hsieh, On vertex ranking of a starlike graph, Information Processing Letters, 82(2002), pp. 131-135.
[10] A.V. Iyer, H.D. Ratliff, and G. Vijayan, Parallel assembly of modular products - an analysis, Technical Report 88-06, Georgia Institute of Technology, 1988.
[11] A.V. Iyer, H.D. Ratliff, and G. Vijayan, Optimal node ranking of trees, Information Processing Letters, 28(1988), pp. 225-229.
[12] T. Kloks, H. Maller, 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.
[13] J.H. Lee. A study of the maximum interval subgraph problem on bipartite permutation graphs. Master Degree Thesis, National Dong Hwa University, Department of Computer Science, 2001.
[14] C.E. Leiserson, Area efficient graph layouts for VLSI, Proc. of the 21th Annual IEEE Symposium on Foundations of Computer Science, 1980, pp. 270-281.
[15] W. Lipski, J.r.,F.P. Preparata, Efficient Algorithm for finding maximum matching in convex bipartite graphs and related problems, Acta Inform, 15(1981), pp. 329-346.
[16] J.W.H. Liu, The role of elimination trees in sparse factorization, SIAM Journal of Matrix Analysis and Applications, 11(1990), pp. 134-172.
[17] A. Pothen, The complexity of optimal elimination trees, Technical Report CS-
88-13, Pennsylvania State University, USA, 1988.
[18] A.A. Schaffer, Optimal node ranking of trees in linear time, Information Processing Letters 33(1989/1990), pp. 91-96.
[19] P. Scheffler, 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.
[20] 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.
[21] J. Spinrad, A. Barndstadt and L. Stewart, Bipartite permutation graphs, Discrete
Applied Mathematics, 18(1987), pp. 279-292.
[22] P. de la Torre, R. Greenlaw, and T.M. Przytycka, Optimal tree ranking is in NC,
Parallel Processing Letters, 2(1992), pp. 31-41.
[23] P. de la Torre, R. Greenlaw, and A.A. Schaffer, Optimal ranking of trees in polynomial time, Proc. of the 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 1993, pp. 138-144.

QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文