跳到主要內容

臺灣博碩士論文加值系統

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

詳目顯示

: 
twitterline
研究生:陳紀綱
研究生(外文):Chi-Kang Chen
論文名稱:一個有效率的演算法解決原始似星圖上的區間圖完成問題
論文名稱(外文):An Efficient Algorithm for the Interval Graph Completion Problem on Primitive Starlike Graphs
指導教授:彭勝龍彭勝龍引用關係
指導教授(外文):Sheng-Lung Peng
學位類別:碩士
校院名稱:國立東華大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文種類:學術論文
論文出版年:2002
畢業學年度:90
語文別:英文
論文頁數:49
中文關鍵詞:區間圖完成問題
外文關鍵詞:Interval graph completion problem
相關次數:
  • 被引用被引用: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 find an interval
supergraph H with the same vertex set as G and the number of added edges is the
minimum. It has been shown that this problem is equivalent to the minimum sum cut
and profile minimization problems. Besides, it can be viewed as a vertex version of the
minimum linear arrangement problem and have well-known applications in archaeology
and clone fingerprinting.
This problem has been shown to be NP-complete on general graphs, and remains
to 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 1
2 Preliminaries 5
2.1 Interval completion 7
2.2 Path-decomposition 8
2.3 Starlike graphs 9
2.4 k-Starlike graphs 12
2.5 Split 12
2.6 Primitive starlike graphs 13
3 Some Properties 15
3.1 Normalized Property 15
3.2 Comparable Property 17
3.3 Strong property 20
4 An $O(n^2)$ Algorithm 25
5 Concluding Remarks 34
Bibliography 35
[1] D. Bienstock, Graph searching, path-width, tree-width and related problems (a
survey), 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 Applications
in the Biosciences, Vol.11, pages 49–57, 1995.

[3] H. L. Bodlaender, T. Kloks, D. Kratsch, and H. M¨uller, Treewidth and minimum
ll-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, ISBN
3-540-52846-6, pages 301–309, 1990.

[5] K. S. Booth and G. S. Lueker, Testing for consecutive ones property, interval graphs
and 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 Monographs
on Discrete Mathematics and Applications, Philadelphia, 1999.

[7] L. Cai, Fixed-parameter tractability of graph modication problems for hereditary
properties, Technical report, Department of Computer Science, The Chinese
University of Hong Kong, Shatin New Territories, Hong Kong, 1995.

[8] T. H. Cormen, C. E. Leiserson, and R. L. Rivest, Introduction to Algorithms, The
MIT 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 Mathematischen
Seminar der Universitat Hamburg, Vol.25, pages 71–76, 1961.

[12] G. Even, J. (Se) Naor, S. Rao, and B. Schieber, Divide-and-conquer approximation
algorithms via spreading metrics, In Proceedings of the 36th Annual Symposium
on Foundations of Computer Science, pages 62–71, October 1995.

[13] S. Foldes and P. L. Hammer, Split graphs, Proc. 8th Southeastern Conference on
Combinatorics, Graph Theory and Computing (F. Homan and et al., eds.), pages
311–315, 1977.

[14] F. V. Fomin and P. A. Golovach, Graph searching and interval completion, SIAM
Journal on Discrete Math., Vol.13, pages 454–464, 2000.

[15] D. R. Fulkerson and O. A. Gross, Incidence matrices and interval graphs, Pacic
Journal of Math., Vol.15, pages 835–855, 1965.

[16] M. R. Garey and D. S. Johnson, Computers and Intractability: A guide to the
Theory of NP-Completeness, Freeman, San Francisco, 1979.

[17] P. C. Gilmore and A. J. Homan, A characterization of comparability graphs and
of 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 against
physical 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, Journal
of Algorithms, Vol.19, pages 449–473, 1995.
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top
無相關論文