臺灣博碩士論文加值系統

對於一個圖形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.