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

(18.208.126.232) 您好！臺灣時間：2022/08/12 00:58

:::

### 詳目顯示

:

• 被引用:0
• 點閱:144
• 評分:
• 下載:8
• 書目收藏:0
 一個圖形中若不含大於長度三的迴路，則我們稱此圖為弦圖。一個圖形G 的樹寬（最少填入邊）問題，即是找一個弦圖包含G，使得最大的完全子圖必須為最小（填入邊數最少）。對一般圖而言，樹寬和最少填入邊問題都是NP-complete，即使在一些特殊圖如雙分圖、雙分圖的補圖等也都是NP-complete。在這一篇論文中我們提出了一個一致的演算法來解決雙分排列圖上樹寬和最少填入邊問題，我們的演算法執行時間是線性的。前人最佳的結果需要花Ｏ(n2)的時間，（n 是輸入圖中點的個數。）
 A graph is chordal if every cycle of length greater than three has a chord. Thetreewidth (respectively, minimum ll-in) problem is to nd a chordal supergraphwith the smallest possible maximum clique size (respectively, the minimum number ofadditional edges). Similarly, the pathwidth (respectively, interval graph completion)problem is to nd a interval supergraph with the smallest possible maximum cliquesize (respectively, the minimum number of additional edges). Both problems are NPcompleteon general graphs. They remain NP-complete even for cobipartite graphs,bipartite graphs and graphs of clique size at most 9. A bipartite permutation graph isa both bipartite and permutation graph. In this thesis, we present a uni ed approachto compute the treewidth and minimum ll-in on bipartite permutation graphs inlinear time. The best previous result is O(n2) where n is the number of vertices inthe input graph.
 Abstract iAcknowledgement iiContents iiiList of Figures vList of Tables vii1 Introduction 12 Preliminaries 72.1 De nitions about related graph classes . . . . . . . . . . . . . . . . . 72.2 Treewidth and minimum ll-in . . . . . . . . . . . . . . . . . . . . . . 133 Main Results 193.1 Biclique . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2 Idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213.3 A uni ed algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 Concluding Remarks 31Bibliography 32
 [1] N. Abbas and L. K. Stewart. Biconvex graphs: ordering and algorithms. DiscreteApplied Mathematics, 103:1{19, 2000.[2] S. Arnborg, D. G. Corneil, and A. Proskurowski. Complexity of nding embeddingsin 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 problemsrestricted to partial k-tree. Discrete Applied Mathematics, 23:11{24, 1989.[4] H. L. Bodlaender. A linear time algorithm for nding tree-decompositions ofsmall treewidth. Proceedings of the 25th Annual ACM Symposium on Theory ofComputing, 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 permutationgraphs. SIAM Journal on Graph Discrete Mathematics, 8:606{616,1995.[7] H. L. Bodlaender, T. Kloks, D. Kratsch, and H. Muller. Treewidth and minimumll-in on d-trapezoid graphs. Journal of Graph Algorithms and Applications, 2:1{23, 1998.[8] H. L. Bodlaender and R. H. Mohring. 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 graphswith small chordality. Technical Report UU-CS-1995-02, Department of ComputerScience, Utrecht University, Utrecht, 1995.[10] H. Broersma, E. Dahlhaus, and T. Kloks. A linear time algorithm for minimumll in and treewidth for distance hereditary graphs. Scienti c program 5th TwenteWorkshop on Graphs and Combinatorial Optimization, pages 48{50, 1997.[11] M. S. Chang. Algorithms for maximum matching and minimum ll-in on chordalbipartite graphs. Proceedings of the 7th International Symposium Algorithms andComputation, 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 MathematischenSeminar der Universitat Hamburg, 25:71{76, 1961.[14] G. A. Dirac. Cographs: recognition, applications and algorithms. CongressusNumerantium, 43:249{258, 1984.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 1 雙凸二分圖上的完全二分子圖結構

 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

 1 一個有效率的演算法解決原始似星圖上的區間圖完成問題 2 一個線性時間演算法建造樹的最小高度消去樹 3 混合式紋理合成技術 4 近似輪廓邊線的萃取 5 基於無線區域環境下之遠端監測網管系統 6 植基於VoronoiDiagram的合成裂痕技術 7 用於行動特殊網路中群播系統應用之權重式叢集路徑選擇演算法 8 在行動網路環境中以代理人為基礎架構的資源保留協定 9 植基於數位傳輸內容保護標準的兩項研究議題:設計具備安全認證機制的隨選視訊和會議金鑰之通訊協定 10 可寫一次光碟防竄改保護技術之研究 11 無線感測網路在醫療資訊管理的應用研究 12 醫院分類:SVMApproach 13 採集合排序樣本時,常態平均值之較佳檢定 14 積分型式的交叉有效法 15 二元數列之預測方法的模擬比較：預測方法是否需具隨機性？

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