跳到主要內容

臺灣博碩士論文加值系統

(18.208.126.232) 您好!臺灣時間:2022/08/12 00:58
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:林俊榮
研究生(外文):Jun-Rong Lin
論文名稱:一個一致的方法解決雙分排列圖上樹寬和最少填入邊問題
論文名稱(外文):A Unified Approach for Treewidth and Minimum Fill-in Problems on Bipartite Permutation Graphs
指導教授:彭勝龍彭勝龍引用關係
指導教授(外文):Sheng-Lung Peng
學位類別:碩士
校院名稱:國立東華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:44
中文關鍵詞:雙分排列圖最少填入邊樹寬
外文關鍵詞:bipartite permutation graphstreewidthminimum fill-in
相關次數:
  • 被引用被引用:0
  • 點閱點閱:144
  • 評分評分:
  • 下載下載:8
  • 收藏至我的研究室書目清單書目收藏:0
一個圖形中若不含大於長度三的迴路,則我們稱此圖為弦圖。一個圖形G 的樹寬(最少填入邊)問題,即是找一個弦圖包含G,使得最大的完全子圖必須為最小(填入邊數最少)。對一般圖而言,樹寬和最少填入邊問題都是NP-complete,即使在一些特殊圖如雙分圖、雙分圖的補圖等也都是NP-complete。在這一篇論文中我們提出了一個
一致的演算法來解決雙分排列圖上樹寬和最少填入邊問題,我們的演算法執行時間是線性的。前人最佳的結果需要花O(n2)的時間,(n 是輸入圖中點的個數。)
A graph is chordal if every cycle of length greater than three has a chord. The
treewidth (respectively, minimum ll-in) problem is to nd a chordal supergraph
with the smallest possible maximum clique size (respectively, the minimum number of
additional edges). Similarly, the pathwidth (respectively, interval graph completion)
problem is to nd a interval supergraph with the smallest possible maximum clique
size (respectively, the minimum number of additional edges). Both problems are NPcomplete
on general graphs. They remain NP-complete even for cobipartite graphs,
bipartite graphs and graphs of clique size at most 9. A bipartite permutation graph is
a both bipartite and permutation graph. In this thesis, we present a uni ed approach
to compute the treewidth and minimum ll-in on bipartite permutation graphs in
linear time. The best previous result is O(n2) where n is the number of vertices in
the input graph.
Abstract i
Acknowledgement ii
Contents iii
List of Figures v
List of Tables vii
1 Introduction 1
2 Preliminaries 7
2.1 De nitions about related graph classes . . . . . . . . . . . . . . . . . 7
2.2 Treewidth and minimum ll-in . . . . . . . . . . . . . . . . . . . . . . 13
3 Main Results 19
3.1 Biclique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2 Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.3 A uni ed algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4 Concluding Remarks 31
Bibliography 32
[1] N. Abbas and L. K. Stewart. Biconvex graphs: ordering and algorithms. Discrete
Applied Mathematics, 103:1{19, 2000.
[2] S. Arnborg, D. G. Corneil, and A. Proskurowski. Complexity of nding embeddings
in a k-tree. SIAM Journal of Algebraic and Discrete Methods, 8:277{284,
1987.
[3] S. Arnborg and A. Proskurowski. Linear time algorithms for NP-hard problems
restricted to partial k-tree. Discrete Applied Mathematics, 23:11{24, 1989.
[4] H. L. Bodlaender. A linear time algorithm for nding tree-decompositions of
small treewidth. Proceedings of the 25th Annual ACM Symposium on Theory of
Computing, pages 226{234, 1993.
[5] H. L. Bodlaender. A tourist guide through treewidth. Acta Cybernetica, 11:1{23,
1993.
[6] H. L. Bodlaender, T. Kloks, and D. Kratsch. Treewidth and pathwidht of permutation
graphs. SIAM Journal on Graph Discrete Mathematics, 8:606{616,
1995.
[7] H. L. Bodlaender, T. Kloks, D. Kratsch, and H. Muller. Treewidth and minimum
ll-in on d-trapezoid graphs. Journal of Graph Algorithms and Applications, 2:1{
23, 1998.
[8] H. L. Bodlaender and R. H. Mohring. The pathwidth and treewidth of cographs.
SIAM Journal on Discrete Mathematics, 6:181{188, 1993.
[9] H. L. Bodlaender and D. M. Thilikos. Treewidth and small separators for graphs
with small chordality. Technical Report UU-CS-1995-02, Department of Computer
Science, Utrecht University, Utrecht, 1995.
[10] H. Broersma, E. Dahlhaus, and T. Kloks. A linear time algorithm for minimum
ll in and treewidth for distance hereditary graphs. Scienti c program 5th Twente
Workshop on Graphs and Combinatorial Optimization, pages 48{50, 1997.
[11] M. S. Chang. Algorithms for maximum matching and minimum ll-in on chordal
bipartite graphs. Proceedings of the 7th International Symposium Algorithms and
Computation, pages 146{155, 1996.
[12] G. Chartrand and O. R. Oellermann. Applied and Algorithmic Graph Theory.
McGraw-Hill, 1993.
[13] G. A. Dirac. On rigid circuit graphs. Abhandlungen aus dem Mathematischen
Seminar der Universitat Hamburg, 25:71{76, 1961.
[14] G. A. Dirac. Cographs: recognition, applications and algorithms. Congressus
Numerantium, 43:249{258, 1984.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
1. 徐享崑、劉豐壽、鄭昌奇(1995),台灣地區地層下陷現況、成因與對策,臺灣水利,第171期,19-29。
2. 林建元、游振偉(1996),工業區開發之區位選擇,工業簡訊,第12期,8-23。
3. 林明鏘(2000),農地釋出之規劃與永續發展,月旦法學,第58期,47-56。
4. 李振誥(1998),地層下陷防治方法之研究,土木技術,第1卷,第1期,68-84。
5. 毛育剛(1997),台灣農地保護政策與措施,人與地,第167/168期,47-54。
6. 陳明燦(2000),我國農地之使用管制:國土規劃法制之觀點,月旦法學,第58期,68-88。
7. 陳明燦(1995),農地釋放與國土規劃政策之探討,理論與政策,第9卷,第3期,83-94。
8. 陶翼煌(1998),應用地理資訊系統於屏東沿海地區地層下陷災害之研究,東南學報,第22期,123-140。
9. 游振偉(1998),工業區規劃開發之發展趨勢,工業簡訊,第28卷,第2期,105-111。
10. 鄭昌奇、柳志錫(1998),台灣地區之地層下陷,土木技術,第1卷,第1期,55-61。
11. 蘇瑞榮(1998),地層下陷防治執行方案之推動,土木技術,第1卷,第1期,62-67。
12. 方翊人,「現金儲值卡與消費者保護相關法律議題之研究」,科技法律透析,第14卷第3期,2002年3月,pp.47~62
13. 方翊人,「網路證券相關法律問題研究」,科技法律透析,第12卷第11期,2000年11月,pp.20~35
14. 王正勤,「網路銀行連通你的荷包」,天下雜誌,188期,1997年1月,pp.46~52
15. 宋振華,「不可否認安全需求及標準規格」,電腦與通訊,94期,2000年12月,pp.70~80