臺灣博碩士論文加值系統

我們說節點集合D ⊆ V 是圖G = (V; E) 的支配子集，指的是在節點集合V \ D 中的每個點都與至少一個D 中的節點相鄰；如果不只是V \ D，D的每個節點也至少與一個D中的節點相鄰的話，我們則稱D 為圖G 的完全支配子集。(完全)支配問題的目標是給定一個圖G，然後找最小的(完全)支配子集D。身為一個經典問題，(完全)支配問題在過去被許多人做過詳盡地研究。近年，支配問題被提出了一個新的沿伸題：分離性支配問題。我們說一個結點集合D ⊆ V 是圖G = (V; E) 的分離性完全支配子集，指的是在V 中的每一個節點不是相鄰於D 中的某些結點，就是有至少兩個在D 中的結點問於距離二的位置。分離性完全支配問題的目標是找出能分離性完全支配圖G的最小子集合D。在計算複雜度方面，我們只知道在任意圖上，分離性完全支配問題是一個NP-困難問題，這代表著我們可能不能在樹上使用傳統的動態規劃法來解這個問題。在這篇論文中，我們藉使用最小費用最大流來處理分離性完全支配問題的子圖，成功設計出第一個在特定圖型類別上的，解分離性完全支配問題的第一個多項式時間演算法。

For a graph G = (V; E), D ⊆ V is a dominating set if every vertex in V \ D has a neighbor in D. If every vertex in V has to be adjacent to a vertex of D, then D is called a total dominating set of G. The (total) domination problem on G is to nd a (total) dominating set D of the minimum cardinality. The (total) domination problem is wellstudied. Recently, the following variant is proposed. A vertex subset D is a disjunctive total dominating set of G if every vertex of V is adjacent to a vertex of D or has at least two vertices in D at distance 2 from it. The disjunctive total domination problem on G is to nd a disjunctive total dominating set D of the minimum cardinality. For the complexity issue, the only known result is that the disjunctive total domination
problem is NP-hard on general graphs. In particular, it seems that a general dynamic programming approach cannot work well for this problem on trees. In this paper, by using a minimum-cost ow algorithm as a subroutine, we show that the disjunctive total domination problem on trees can be solved in polynomial time. This is the first polynomial-time algorithm for the problem on a special class of graphs.

1 Introduction 1
2 Previous works 5
2.1 Total domination algorithm . . . . . . . . . . . . . . . . . . . . 5
2.2 Disjunctive domination algorithm . . . . . . . . . . . . . . . . . 6
2.3 Minimum-cost ow . . . . . . . . . . . . .. . . . . . . . . . . . . 7
2.4 NP-completeness . . . . . . . . . . . . .. . . . . . . . . . . . . 7
3 Algorithm 11
3.1 Traditional algorithm . . . . . . . . . .. . . . . . . . . . . . . 12
3.2 Main algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2.1 Labeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
ii3.2.2 Spanning phase . . . . . . . . . . . . . . . . . . . . . . . . 16
3.2.3 Flow network phase . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.4 Updating phase . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.2.5 Iterate until all the vertices are disjunctively total dominated 20
3.2.6 Time complexity . . . . . . . . . . . . . . . . . . . . . .. . . 23
4 Conclusion and future work 25

[1] Ravindra K. Ahuja and James B. Orlin. A capacity scaling algorithm for the constrained maximum ow problem. Networks, 25(2):8998, 1995.
[2] Kellogg S. Booth and J. Howard Johnson. Dominating sets in chordal graphs. SIAM J. Comput., 11(1):191199, 1982.
[3] Gerard J. Chang. Labeling algorithms for domination problems in sun-free chordal graphs. Discrete Applied Mathematics, 22(1):2134, 1988.
[4] Julia Chuzhoy, Yury Makarychev, Aravindan Vijayaraghavan, and Yuan Zhou. Approximation algorithms and hardness of the k-route cut problem. ACM Trans. Algorithms, 12(1):2, 2016.
[5] Joanna Cyman and Joanna Raczek. Total outer-connected domination numbers of trees. Discrete Applied Mathematics, 157(15):31983202, 2009.
[6] Odile Favaron and Michael A. Henning. Upper total domination in claw-free graphs. Journal of Graph Theory, 44(2):148158, 2003.
[7] Odile Favaron and Michael A. Henning. Paired-domination in claw-free cubic graphs. Graphs and Combinatorics, 20(4):447456, 2004.
[8] Michael A. Henning. Graphs with large total domination number. Journal of Graph Theory, 35(1):2145, 2000.
[9] Michael A. Henning. A survey of selected recent results on total domination in graphs. Discrete Mathematics, 309(1):3263, 2009.
[10] Michael A. Henning and Sinclair A. Marcon. Domination versus disjunctive domination in trees. Discrete Applied Mathematics, 184:171177, 2015.
[11] Michael A. Henning and Viroshan Naicker. Bounds on the disjunctive total domination number of a tree. Discussiones Mathematicae Graph Theory, 36(1):153 171, 2016.
[12] Michael A. Henning and Viroshan Naicker. Disjunctive total domination in graphs. J. Comb. Optim., 31(3):10901110, 2016.
[13] Michael A. Henning and Anders Yeo. Total domination in graphs. 2013.
[14] Michael Anthony Henning and Viroshan Naicker. Graphs with large disjunctive total domination number. Discrete Mathematics & Theoretical Computer Science, 17(1):255282, 2015.
[15] Michael S. Jacobson and Kenneth Peters. Chordal graphs and upper irredundance, upper domination and independence. Discrete Mathematics, 86(1-3):59 69, 1990.
[16] J. Mark Keil. The complexity of domination problems in circle graphs. Discrete Applied Mathematics, 42(1):5163, 1993.
[17] Péter Kovács. Minimum-cost ow algorithms: an experimental evaluation. Optimization Methods and Software, 30(1):94127, 2015.
[18] Dieter Kratsch and Lorna Stewart. Total domination and transformation. Inf. Process. Lett., 63(3):167170, 1997.
[19] Harold W. Kuhn. The hungarian method for the assignment problem. 2003.
[20] James K. Lan and Gerard Jennhwa Chang. On the algorithmic complexity of k-tuple total domination. Discrete Applied Mathematics, 174:8191, 2014.
[21] Alice Anne McRae. Generalizing NP-completeness Proofs for Bipartite Graphs and Chordal Graphs. PhD thesis, Clemson, SC, USA, 1995. UMI Order No.GAX95-18192.
[22] Sandra L. Mitchell, Ernest J. Cockayne, and Stephen T. Hedetniemi. Linear algorithms on recursive representations of trees. J. Comput. Syst. Sci., 18(1):76 85, 1979.
[23] Haiko Müller and Andreas Brandstädt. The np-completeness of steiner tree and dominating set for chordal bipartite graphs. Theor. Comput. Sci., 53:257265, 1987.
[24] B. S. Panda and Arti Pandey. Complexity of total outer-connected domination problem in graphs. Discrete Applied Mathematics, 199:110122, 2016.
[25] B. S. Panda, Arti Pandey, and S. Paul. Algorithmic aspects of disjunctive domination in graphs. pages 325336, 2015.
[26] G. Ramalingam and C. Pandu Rangan. Total domination in interval graphs revisited. Inf. Process. Lett., 27(1):1721, 1988.
[27] S. M. Hedetniemi Renu Laskar, John Pfa and S. T. Hedetneimi. On the algorithmic complexity of total domination. SIAM. J. on Algebraic and Discrete Methods, 5(3):420425.
[28] Jan Arne Telle. Complexity of domination-type problems in graphs. Nord. J. Comput., 1(1):157171, 1994.
[29] Volker Turau and Sven Köhler. A distributed algorithm for minimum distance-k domination in trees. J. Graph Algorithms Appl., 19(1):223242, 2015.
[30] Yancai Zhao and Erfang Shan. An ecient algorithm for distance total domination in block graphs. J. Comb. Optim., 31(1):372381, 2016.