臺灣博碩士論文加值系統

本論文提出一個演算法來解決仙人掌圖上的成對支配點問題。試想一個由點與線構成的圖,支配集是圖上的點構成的點集合,而圖上每個不在支配集裡的點都會至少與一個在支配集裡的點相鄰,如此就構成了支配集。而對於一個圖上的成對支配點集來說,既滿足支配集的定義又滿足支配集裡點形成的誘導子圖上,點兩兩成對。在一個圖上無數成對支配集中,如何找到一個成對支配集且此集合點的數量為無數成對支配點中最少的,就是成對支配點問題。此外,只要一張連通圖是由許多環或邊組成,且任意兩環只會有一個共同交點,就稱之為仙人掌圖。仙人掌圖常用於無線網路的模型中,而成對支配集可以用來解決資源配置以及備份的問題。
在此篇論文中,給予一個仙人掌圖G,令n為點之數量,我們提出了一個可在O(n)時間內找出在G上之最小成對支配點集合的演算法。

A set S⊆V is a dominating set of a graphG=(V,E) if every vertex not in S is adjacent to a vertex in S. A dominating set S of a graph G is called a paired-dominating set if the induced subgraph G[S] contains a perfect matching. The paired-domination problem is to find the paired-dominating set of a graph with minimum size. A block in a graph G is a maximal connected subgraph of G without cut vertices. A cactus graph is a connected graph in which each block is either an edge or a cycle. Any two simple cycles have at most one vertex in common. Cactus graph usually used to model wireless network in some situation, and paired-domination problem can be used to solve problems of resource allocation and backup.
In this thesis, we provide a greedy method algorithm with O(n)-time for the paired-domination problem on cactus graphs.

口試委員會審定書 iii
誌謝 v
摘要 vii
Abstract ix
Introduction 1
Finding a minimum paired-dominating set on cactus graphs 9
Correctness of the algorithm 25
Conclusion 33
Bibliography 35

[1] A. V. Aho, J. E. Hopcroft, and J. D. U. I. man. The design and analysis of computer algorithms. Addison Wesley, 1974.
[2] B. Ben-Moshe, A. Dvir, M. Segal, and A. Tamir. Centdian computation in cactus graphs. Journal of Graph Algorithms and Applications, 16:199–224, 2012.
[3] M. Blidia, M. Chellali, and L. Volkmann. On the p-domination number of cactus graphs. Discussiones Mathematicae Graph Theory, 2005.
[4] M. Chellali. Bounds on the 2-domination number in cactus graphs. Opuscula Mathematica, 26, 2006.
[5] L. Chen, C. Lu, and Z. Zeng. Hardness results and approximation algorithm for (weighted) paired-domination in graphs. Theoretical Computer Science, 410:47–49, 2009.
[6] L. Chen, C. Lu, and Z. Zeng. A linear-time algorithm for paired- domination problem in strongly chordal graphs. Information Processing Letters, 110:20–23, 2009.
[7] L. Chen, C. Lu, and Z. Zeng. Labelling algorithms for paired- domination problems in block and interval graphs. Journal of Combinatorial Optimization, 19:457–470, 2010.
[8] L. Chen, C. Lu, and Z. Zeng. Vertices in all minimum paired- dominating sets of block graphs. Journal of Combinatorial Optimization, 24:179–191, 2012.
[9] T. Cheng, L. Kang, and C. Ng. Paired domination on interval and circular-arc graphs. Discrete Applied Mathematics, 155:2077– 2086, 2007.
[10] T. Cheng, L. Kang, and E. Shan. A polynomial-time algorithm for the paired-domination problem on permutation graphs. Discrete Applied Mathematics, 157:262–271, 2009.
[11] K. Das and M. Pal. An optimal algorithm to find maximum and minimum height spanning trees on cactus graphs. Advanced Modeling and Optimization, 10:121–134, 2008.
[12] X. gang Chen, L. Sun, and H. ming Xing. Characterization of graphs with equal domination and connected domination numbers. Discrete Mathematics, 289:129–135, 2004.
[13] T. W. Haynes, S. Hedetniemi, and P. Slater. Domination in Graphs: Advanced Topics. Marcel Dekker, 1998.
[14] T. W. Haynes, S. Hedetniemi, and P. Slater. Fundamentals of Domination in Graphs. CRC Press, 1998.
[15] T. W. Haynes, S. Hedetniemi, and P. Slater. Paired-domination in graphs. Networks, 32:199–206, 1998.
[16] S. Hedetniemi, R. Laskar, and J. Pfaff. A linear algorithm for finding a minimum dominating set in a cactus. Discrete Applied Mathematics, 13:287–292, 1986.
[17] W.-K. Hon, C.-S. Liu, S.-L. Peng, and C. Y. Tang. Power domination on block-cactus graphs. Combinatorial Mathematics and Computation Theory, 24, 2007.
[18] L. Kanga, M. Y. Sohnb, and T. Chengc. Paired-domination in inflated graphs. Theoretical Computer Science, 320:485–494, 2004.
[19] O. Kariv and S. L. Hakimi. An algorithmic approach to network location problems, part 1: The p-center. SIAM J. Appl. Math, 37:513– 537, 1979.
[20] W. L. G. Koontz. Economic evaluation of loop feeder relief alternatives. Bell System Technical Journal, 1980.
[21] Y. F. Lan and Y. L. Wang. An optimal algorithm for solving the 1-median problem on weighted 4-cactus graphs. European Journal of Operational Research, 122:602–610, 2000.
[22] J. K. Lana and G. J. Chang. On the mixed domination problem in graphs. Theoretical Computer Science, 476, 2013.
[23] J. K. Lana and G. J. Chang. On the algorithmic complexity of k-tuple total domination. Discrete Applied Mathematics, 174:81–91, 2014.
[24] E. Lappas, S. D. Nikolopoulos, and L. Palios. An o(n)-time algorithm for the paired-domination problem on permutation graphs. European Journal of Combinatorics, 34:593–608, 2013.
[25] C.-C. Lin and H.-L. Tu. Linear-time algorithms for the paired-domination problem in interval graphs and circular-arc graphs. Theoretical Computer Science, 2014.
[26] S. Park, B. Kim, E. Lee, D. Lee, Y. Choi, and S.-H. Kim. A novel communication architecture to support mobile users in wireless sensor fields. IEEE Vehicular Technology Conference, pages 66–70, 2007.
[27] H. Qiao, L. Kang, M. Cardei, and D.-Z. Du. Paired-domination of trees. Journal of Global Optimization, 25:43–54, 2003.
[28] D. Saxena. Security in wireless sensor networks - a layer based classification. CERIAS Tech Report, 2007.
[29] H. Wang, P.-Y. Kong, W. Seah, and K. Guan. A robust and energy efficient routing scheme for wireless sensor networks. International Conference Workshops on Distributed Computing Systems, pages 83–89, 2006.
[30] J. Yick and D. Ghosal. Wireless sensor network survey. Computer Networks, 52:2292–2330, 2008.
[31] M. Z. Zamalloa, K. Seada, and A. Helmy. Estimating the traffic on weighted cactus networks in linear time. International Conference on Information Visualization, pages 536–541, 2005.
[32] M. Z. Zamalloa, K. Seada, and A. Helmy. Efficient geographic routing over lossy links in wireless sensor networks. ACM Trans- actions on Sensor Networks, 4:1–33, 2008.