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

(44.201.97.0) 您好！臺灣時間：2024/04/14 04:53

:::

### 詳目顯示

:

• 被引用: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, DiscreteApplied Mathematics, 103(2000), pp. 1-19.[2] H.L. Bodlaender, J.S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Muller, andZs. 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, Approximatingtreewidth, 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 rankingproblem 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 symmetriclinear 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, DiscreteApplied 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.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 1 鄭崇趁（民87）。輔導中輟學生的權責與方案。學生輔導通訊。55期 2 鄧煌發（民89）。輟學少年之家庭與社會學習因素的比較分析。犯罪學期刊，5期，233-276頁。 3 黃德祥、向天屏（民 88）。中輟生形成原因與對策之研究。訓育研究，38（2），16-33頁。 4 林明地（民85）。學校與社區關係－從家長參與學校活動的理念談起。教育研究雙月刊， 51期，32-34頁。 5 甄曉蘭（民84）。合作行動研究－進行教育行動研究的另一種方式。嘉義師院學報。第九期。頁297-318 。 6 蔡德輝、吳芝儀(民90)。為中輟學生籌設選替性另類學校之必要性。翰林文教雜誌第五卷期。 7 王恩祥( 民88 )。教育部推動多元形式「中途學校」專案報告。福利社會，第64卷期。1-4頁。

 1 雙凸二分圖上的完全二分子圖結構 2 雙凸二分圖上的樹寬和徑寬問題 3 靜態programslicing的語義分析方法 4 無線網路WEP-like系統已知IV攻擊法的增強研究 5 新型非二元聽覺式秘密分享系統 6 不變動IV和祕密金鑰長度下讓IEEE802.11b無線網路協定抵抗keystream重複使用攻擊以及已知IV攻擊 7 藍芽與IEEE802.11互連網路之智慧型切換系統設計 8 以環場影像陣列建構虛擬實境之研究 9 資料探勘於線上咨詢系統之研究---提供感興趣之關聯規則與昂貴規則 10 動態物件電影 11 部分多重週期性無重複樣式的有效率探勘方法 12 通用存取之隨選媒體系統設計 13 整合性服務及差異性服務排程結合之服務品質策略設計 14 IPv4/IPv6轉換機制之效能研究 15 ProceduralAbstraction應用在程式最佳化的研究

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