臺灣博碩士論文加值系統

令G=(V,E)表示一個圖形。我們稱一個點集合W 為G 的支配集合
若集合V 中的每個不存在於W 中的點都至少有一個鄰點存在於W。若
點集合W 內部所有點之間互不相鄰則稱W 為獨立支配集合。圖G 上
的(獨立)支配問題就是找出一個含點個數最少的(獨立)支配集合。
圖G 若存在一個可對應至實線上的區間集且這些區間可以一一對
應至G 中的點，即G 中兩點相鄰若且惟若對應到的區間有相交，則稱
G 為區間圖。圖G=(V,E)為一個探針區間圖，若點集合V 可以分為兩個
子集合，探針集合P 和一個為獨立集合的非探針集合N，使得G 在非
探針集合N 中新增一些連線後，可被嵌入至一個區間圖。在這篇論文
中，我們提出了多項式時間演算法來解決探針區間圖中的支配和獨立
支配問題。

Let G = (V; E) be a graph. A vertex setW µ V is a dominating set of G if every vertex
of V is either in W or adjacent to a vertex in W. A dominating set W is independent
if there is no edge between any two vertices of W. The (independent) domination
problem of G is to ‾nd a (independent) dominating set W with minimum cardinality.
A graph G is an interval graph if there is a collection of intervals on the real line
and a 1-1 mapping from the vertices of G to these intervals, such that two vertices are
adjacent if and only if their corresponding intervals intersect. A graph G = (V; E) is a
probe interval graph if V can be partitioned into a set P of probes and an independent
set N of nonprobes such that G can be embedded into an interval graph by adding some
edges between vertices of N. In this thesis we propose polynomial-time algorithms
for solving the domination and the independent domination problems on probe
interval graphs.

Abstract i
Contents ii
List of Figures iv
1 Introduction 1
2 Preliminaries 4
2.1 Probe Interval Graphs 4
2.2 Domination Problem 7

2.3 Independent Domination Problem 9
3 Algorithm for domination 11
3.1 Notation 12
3.2 Intersection 14
3.3 Algorithm 18
4 Algorithm for independent domination 25
4.1 Notation 25
4.2 Algorithm 26
5 Concluding remarks 31
Bibliography 32

[1] K. S. Booth, J. H. Johnson, Dominating sets in chordal graphs, SIAM J. Comput.
11(1982), pp. 191{199.
[2] K. S. Booth and G. S. Lueker, Testing for the consecutive ones property, interval
graphs, and graph planarity using PQ-tree algorithms, Journal of Computer and
System Sciences 13(1976), pp. 335{379.
[3] A. BrÄandstadt, V. Le, and J. P. Spinrad, Graph classes: A survey SIAM Mono-
graphs on Discrete Mathematics and Applications, Philadelphia, 1999.
[4] G. J. Chang, A. J. J. Kloks, J. Liu, and S.-L. Peng, The PIGs full monty|A
°oor show of minimal separators, Proceedings STACS 2005 , LNCS 3404(2005),
pp. 521{532.
[5] M. S. Chang, E±cient algorithms for the domination problems on interval and
circular-arc graphs, SIAM J. Comput., 27(1998), pp. 1671{1694.
[6] M. Chudnovsky, P. Seymour, N. Robertson, and R. Thomas, The strong perfect
graph theorem. Manuscript 2002.
[7] E. J. Cockayne, O. Favaron, C. Payan, and A. Thomason, Contributins to the
theory of domination, independence, and irredundance in graphs, Discrete Math.
33(1981), pp. 249{258.
[8] D. G. Corneil and Y. Perl, Clustering and domination in perfect graphs, Discrete
Application Mathmetics, 9(1984), pp27-39.
[9] F.R. McMorris, C. Wang, and P. Zhang, On probe interval graphs, Discrete
Applied Mathematics, vol.88, pp.315V324, 1998.
[10] P. Damaschke, H. Muller, and D. Kratsch, Domination in convex and chordal
bipartite graphs, Inform. Process. Lett., 36(1990), pp. 231-236.
[11] M. Farber, Independent domination in chordal graphs, Operations Research Let-
ters, 1(1982), pp. 134-138.
[12] M. C. Golumbic, Algorithmic Graph Theory and Perfect Graphs, Academic
Press, New York, 1980.
[13] M. C. Golumbic and A. N. Trenk, Tolerance graphs, Cambridge University Press
2003.
[14] M. GrÄotschel, Characterizations of perfect graphs, Mathematical Programming
Society Newsletter 62, 1999.
[15] M. GrÄotschel, L. Lov¶asz, and A. Schrijver, The ellipsoid method and its con-
sequences in combinatorial optimization, Combinatorica 1(1981), pp. 169{197.
Corrigendum: Combinatorica 4(1984), pp. 291{295.
[16] M. Haiko and B. Andreas, The NP-completeness of Steiner tree and dominating
set for chordal bipartite graphs. Theor. Comput. Sci. 53(1987), pp. 257{265.
[17] A. Hajnal, J. sur¶anyi, ÄUber die Au°Äosung von Graphen in vollstÄandige Teil-
graphen, Ann. Univ. Sci. Budapest, EÄotvÄos. Math. 1(1958), pp. 113-121.
[18] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (Eds.), Domination in graphs:
Advanced Topics, Marcel Dekker, Inc., New-York, 1998.
[19] R. B. Hayward, Weakly triangulated graphs, J. Combin. Theory B 39(1985),
pp. 200{208.
[20] R. B. Hayward, C. Ho¶ang, and F. Ma®ray, Optimizing weakly triangulated
graphs, Graphs and Combinatorics 5(1990), pp. 33{35.
[21] S. Hougardy, Inclusions between classes of perfect graphs. Preprint, Institut fÄur
Informatik, Humboldt{UniversitÄat zu Berlin, (1998).
[22] S. C. Hedetniemi and R. Laskar, eds., Topics on domination, Annals on Discrete
Mathematics 48, North{Holland, Amsterdam 1991.
[23] R. Irving, On approximating the minimum independent dominating set. Inform.
Proc. Lett., 37(1991), pp. 197-200.
[24] J. L. Johnson and J. Spinrad, A polynomial time recognition algorithm for
probe interval graphs, Proceedings 12th ACM{SIAM Symposium on Discrete
Algorithms (2001), pp. 477{486.
[25] D. Kratsch, Domination and total domination in asteroidal triple-free graphs,
Discrete Appl. Math. 99(2000), pp. 111{123.
[26] R. M. McConnell and J. Spinrad, Construction of probe interval graphs, Proceed-
ings 13th ACM{SIAM Symposium on Discrete Algorithms (2002), pp. 866{875.
[27] F. R. McMorris, C. Wang, and P. Zhang, On probe interval graphs, Discrete
Applied Mathematics 88(1998), pp. 315{324.
[28] P. Zhang, Probe interval graph and its application to physical mapping of DNA.
Manuscript 1994.
[29] P. Zhang, E. A. Schon, S. G. Fisher, E. Cayanis, J. Weiss, S. Kistler, and P.
E. Bourne, An algorithm based on graph theory for the assembly of contigs in
physical mapping of DNA, CABIOS 10(1994), pp. 309{317.