臺灣博碩士論文加值系統

(44.200.171.74) 您好！臺灣時間：2022/08/12 20:44

:::

詳目顯示

:

• 被引用:0
• 點閱:172
• 評分:
• 下載:16
• 書目收藏:1
 對於一個圖形G=(V,E)，interval graph completion 問題的目的是要找到一個interval supergraph H=(V,F)，而且對於所有可能的interval supergraphs，H所加入的edge數目必須為最少。目前已經知道minimum sum cut 問題，profile minimization 問題與interval graph completion 問題其實是一樣的問題，不僅如此，這個問題還是minimum linear arrangement 問題的點版本，在考古學與指紋辨識學的領域中，有很重要的應用角色。對於一般圖來說，interval graph complete 問題是一個NP-complete的問題。而且就算是在edge graphs與cobipartite graphs上，也仍然都是NP-complete的問題。我們在這一篇論文中提出了一個演算法，能夠在O(n2)的時間內解決primitive starlike graphs上的interval graph complete 問題。
 The Interval Graph Completion Problem for a given graph G is to ﬁnd an intervalsupergraph H with the same vertex set as G and the number of added edges is theminimum. It has been shown that this problem is equivalent to the minimum sum cutand proﬁle minimization problems. Besides, it can be viewed as a vertex version of theminimum linear arrangement problem and have well-known applications in archaeologyand clone ﬁngerprinting.This problem has been shown to be NP-complete on general graphs, and remainsto be NP-complete on edge graphs and cobipartite graphs. In this thesis, we give an\$O(n^2)\$-time algorithm to solve this problem on a primitive starlike graph with n vertices.
 1 Introduction 12 Preliminaries 52.1 Interval completion 72.2 Path-decomposition 82.3 Starlike graphs 92.4 k-Starlike graphs 122.5 Split 122.6 Primitive starlike graphs 133 Some Properties 153.1 Normalized Property 153.2 Comparable Property 173.3 Strong property 204 An \$O(n^2)\$ Algorithm 255 Concluding Remarks 34Bibliography 35
 [1] D. Bienstock, Graph searching, path-width, tree-width and related problems (asurvey), DIMACS Ser. Discrete Mathematics and Theoretical Computer Science 5,Amer. Math. Soc., Providence, RI, pages 33–49, 1991.[2] H. L. Bodlaender, R.G. Downey,M. R. Fellows,M. T. Hallett, and H. T. Wareham,Parameterized complexity analysis in computational biology, Computer Applicationsin the Biosciences, Vol.11, pages 49–57, 1995.[3] 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, Vol.2,No.5, pages 1–23, 1998.[4] H. L. Bodlaender and R. H. M¨ohring, The pathwidth and treewidth of cographs,2nd Scandinavian Workshop on Algorithm Theory, Bergen, Norway, July 11-14,1990. Proceedings of Lecture Notes in Computer Science, Vol.447, Springer, ISBN3-540-52846-6, pages 301–309, 1990.[5] K. S. Booth and G. S. Lueker, Testing for consecutive ones property, interval graphsand planarity using pq-tree algorithms, Journal of Computer Systems Science, Vol.13, pages 335–379, 1976.[6] A. Brandstadt, V.B. Le, and J.P. Spinrad, Graph classes—a survey, SIAM Monographson Discrete Mathematics and Applications, Philadelphia, 1999.[7] L. Cai, Fixed-parameter tractability of graph modication problems for hereditaryproperties, Technical report, Department of Computer Science, The ChineseUniversity of Hong Kong, Shatin New Territories, Hong Kong, 1995.[8] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, TheMIT Press and McGraw-Hill Book Company, 1999.[9] J. Diaz, A. M. Gibbons, M. S. Paterson, and J. Toran, The minsumcut problem,In F. Dehen, R. J. Sack and N. Santoro editors, Algorithms and Data structure,Lecture Notes in Computer Science, Vol.519, pages 65–79, 1991.[10] J. Diaz, J. Petit, and M. Serna, A survey on graph layout problems, 2000.[11] G. A. Dirac, On rigid circuit graphs, Abhandlungen aus dem MathematischenSeminar der Universitat Hamburg, Vol.25, pages 71–76, 1961.[12] G. Even, J. (Se) Naor, S. Rao, and B. Schieber, Divide-and-conquer approximationalgorithms via spreading metrics, In Proceedings of the 36th Annual Symposiumon Foundations of Computer Science, pages 62–71, October 1995.[13] S. Foldes and P. L. Hammer, Split graphs, Proc. 8th Southeastern Conference onCombinatorics, Graph Theory and Computing (F. Homan and et al., eds.), pages311–315, 1977.[14] F. V. Fomin and P. A. Golovach, Graph searching and interval completion, SIAMJournal on Discrete Math., Vol.13, pages 454–464, 2000.[15] D. R. Fulkerson and O. A. Gross, Incidence matrices and interval graphs, PacicJournal of Math., Vol.15, pages 835–855, 1965.[16] M. R. Garey and D. S. Johnson, Computers and Intractability: A guide to theTheory of NP-Completeness, Freeman, San Francisco, 1979.[17] P. C. Gilmore and A. J. Homan, A characterization of comparability graphs andof interval graphs, Canadian Journal of Mathematics, Vol.16, pages 539–548, 1964.[18] P. W. Goldberg, M. C. Golumbic, H. Kaplan, and R. Shamir, Four strikes againstphysical mapping of dna, Journal of Computational Biology, Vol.2, pages 139–152,1995.[19] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic Press,Inc., 1980.[20] M. C. Golumbic, H. Kaplan, and R. Shamir, Graph sandwich problems, Journalof Algorithms, Vol.19, pages 449–473, 1995.
 電子全文
 國圖紙本論文
 推文當script無法執行時可按︰推文 網路書籤當script無法執行時可按︰網路書籤 推薦當script無法執行時可按︰推薦 評分當script無法執行時可按︰評分 引用網址當script無法執行時可按︰引用網址 轉寄當script無法執行時可按︰轉寄

 無相關論文

 1 侯錦雄（1994），未央歌的重現-大學校園戶外空間的意象性，造園季刊，頁18-24。 2 侯錦雄、姚靜婉（1997），市民休閒生活態度與公園使用滿意度之相關研究，戶外遊憩研究，10（3），1-17。 3 許伯元（1996），以人本及科際整合為目標的理想城---談東華大學的校園規劃，建築師，05，頁74-75。 4 郭瓊瑩（1994），人性空間尊嚴---談校園環境之空間品質與人文精神，造園季刊，頁10-17。 5 彭康健（1993），大學校園的空間模式，建築師，01，90-99。 6 蔡元良（1996），當校園中央草地與清明上河圖相會---評東華大學校園規劃與建築，建築師，05，100-105。 7 1. 劉建光，如何應付巨災危險；保險專刊 第31輯 ；82年3月；P64~68.

 1 一個線性時間演算法建造樹的最小高度消去樹 2 一個一致的方法解決雙分排列圖上樹寬和最少填入邊問題 3 用於行動特殊網路中群播系統應用之權重式叢集路徑選擇演算法 4 可寫一次光碟防竄改保護技術之研究 5 使用資料隱藏的影像竄改回覆技術 6 應用於封包交換器之公平排程演算法的設計與實作 7 混合式紋理合成技術 8 近似輪廓邊線的萃取 9 基於無線區域環境下之遠端監測網管系統 10 植基於VoronoiDiagram的合成裂痕技術 11 在行動網路環境中以代理人為基礎架構的資源保留協定 12 植基於數位傳輸內容保護標準的兩項研究議題:設計具備安全認證機制的隨選視訊和會議金鑰之通訊協定 13 藍芽個人區域網路之服務品質規劃與分析 14 醫院分類:SVMApproach 15 採集合排序樣本時,常態平均值之較佳檢定

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