臺灣博碩士論文加值系統

電力控制問題就是在一個圖G上，找到能透過柯霍夫觀測法則且使用最少的點數，觀測到圖上所有點的方法，此問題已經被證實在一般圖上是NP-complete的問題。在本篇論文中，我們在一類特殊圖上(蜂巢圖)，找到此問題的最佳解法，並且使用的時間複雜度是O (n)，其中n為蜂巢圖的大小。我們在附錄提供了一個小程式，可以測試任意一個任意大小的點子集合，是否可讓全蜂巢圖的點都被觀測到。

Given a graph G = (V, E), the power domination problem is to find a minimum vertex set

Contents
致謝........................................................................................................................................ I
Acknowledgements ............................................................................................................. II
論文摘要.............................................................................................................................. III
Abstract ............................................................................................................................... IV
Contents ............................................................................................................................... V
List of Figures ....................................................................................................................VII
List of Tables ................................................................................................................... VIII
Chapter 1 Introduction ...........................................................................................1
1.1. Definition of the Power Domination Problem ........................................................1
1.2. Previous Work .........................................................................................................2
1.3. Meshes ....................................................................................................................3
1.4. Honeycomb Meshes ................................................................................................4
1.5. Our Contribution .....................................................................................................5
Chapter 2 Notation ..................................................................................................6
2.1. Basic Definition ......................................................................................................7
Chapter 3 Main Result............................................................................................9
3.1. Our Algorithm .........................................................................................................9
3.2. Correctness ............................................................................................................10
3.3. Lower Bound ........................................................................................................12
Chapter 4 Conclusion ...........................................................................................15
4.1. Conjecture .............................................................................................................15
4.2. Future Work ..........................................................................................................16
Appendix ..............................................................................................................................17
A.1. The Source Code ...................................................................................................17
A.2. Performance ..........................................................................................................33
References ............................................................................................................................37

[1] Ashkan Aazami, Domination in Graphs with Bounded Propagation: Algorithms, Formulations and Hardness Results, Journal of Combinatorial Optimization, DOI10.1007/s10878-008-9176-7.
[2] Ashkan Aazami and Michael David Stilp, Approximation Algorithms and Hardness for Domination with Propagation, Lecture Notes In Computer Science 4627, 1-15, 2007.
[3] M. Chen, K. G. Shin and D.D. Kandlur, Addressing, Rounting, and Broadcasting in Hexagonal Mesh Multiprocessors, IEEE Transactions on Computer 39 (1), 10-18, 1990.
[4] Michael Dorfling and Michael A. Henning, A note on power domination in Grid Graphs, Discrete Applied Mathematics 154, 1023-1027, 2006.
[5] Paul Dorbec, Michel Mollard, Sandi Klavzar, and Simon Spacapan, Power Domination in Product Graphs, SIAM Journal on Discrete Mathematics 22 (2), 554-567, 2008.
[6] Jiong Guo, Rolf Niedermeier, and Daniel Raible, Improved Algorithms and Complexity Results for Power Domination in Graphs, Algorithmica 52 (2), 177-202, 2008.
[7] T. W. Haynes, S. M. Hedetiemi, S. T. Hedetiemi, and M. A. Henning, Power Domination in Graphs Applied to Electrical Power Networks, SIAM J. Discrete Math. 15(4), 519-529, 2002.
[8] Wing-Kai Hon, Chih-Shan Liu, Sheng-Lung, and Chuan-Yi Tang, Power Gomination on Glock-Cactus Graphs, Proceedings of The 24th Workshop on Combinatorial Mathematics and Computation Theory, 280-2284, 2007.
[9] Chung-Shou Liao and Der-Tsai Lee, The Power Domination Problem in Graphs, Lecture Notes in Computer Science 3595, 818-828, 2005.
[10] V. Milutinovic, Mapping of neural networks on the honeycomb architecturesm, Proceedings of the IEEE 77 (12), 1875-1878, 1989
[11] F. G. Nocetti, I. Stojmenovic and J. Zhang, Addressing and Routing in Hexagonal Networks with Applications for Tracking Mobile Users and Connection Rerouting in Cellular Network, IEEE Transactions on Parallel and Distributed Systems 13 (9), 963-971, 2002.
[12] J. Kneis, D. Molle, S. Richter, and P. Rossmanith, Parameterized Power Domination Complexity , Information Processing Letters 98, 145-149, 2006.
[13] Kung-Jui Pai, Jou-Ming Chang, and Yue-Li Wang, A Simple Algorithm for Solving the Power Domination Problem on Grid Graphs, Proceedings of The 24th Workshop on Combinatorial Mathematics and Computation Theory, 256-260, 2007.
[14] Daniel Raible and Henning Fernau, Power Domination in O* (1.7548n) Using Reference Search Trees, Lecture Notes In Computer Science 5369, 136-147, 2008.
[15] Ivan Stojmenovic, Honeycomb Networks Topological Properties and Communication Algorithms, IEEE Transactions on Parallel and Distributed Systems 8(10), 1036-1042, 1997.
[16] Guangiun Xu, Liying Kang, Erfang Shan, and Min Zhao, Power Domination in Block Graphs, Theoretical Computer Science 359, 299-305, 2006.