臺灣博碩士論文加值系統

本篇論文分成兩個部分。第一部分考慮完全二分圖K_(m,n)的符號星控制數γ_SS (K_(m,n) )與符號星劃分數d_SS (K_(m,n) )。雖然γ_SS (K_(m,n) )與d_SS (K_(m,n) )在本篇論文之前就已經被討論過，但是都需要再釐清一些證明的推導。在本篇論文中，我們將對γ_SS (K_(m,n) )與d_SS (K_(m,n) )給出一個新的推導。本篇論文的第二部分則是考慮在許多感測網路協定中的一個重要的技術，也就是網路平面化。網路平面化的目的在對於一個給定的無線感測網路，得到一個連通的平面生成子圖，使得該平面子圖能被使用在各種不同的應用上（例如：地理路由、拓樸發現）。然而，網路平面化是一個困難的問題，目前知名又有效率的平面化演算法都只適用在單位圓盤圖並且已知位置資訊。在論文[20]中，Zhang等三位學者發表了一個適用於更一般化的網路模型的平面化演算法，該模型中無線感測器的傳輸半徑不需要一致，甚至連位置資訊都不需要。在本篇論文的第二部分，我們將會改進Zhang等人的平面化演算法，並且利用模擬來證明我們的演算法有更好的表現。

1 Introduction 1
2 The signed star domination and domatic numbers of Km;n 5
2.1 The signed star domination number of Km;n 6
2.2 The signed star domatic number of Km;n 9
3 The planarization algorithm 12
3.1 The ZJC-algorithm 13
3.2 Our improved planarization algorithm 18
3.2.1 Our improved method to choose nodes into the layers 19
3.2.2 Simulation and Performance 21
4 Concluding remarks 27

[1] M. Atapour, S. M. Sheikholeslami, A. N. Ghameshlou and L. Volkmann, Signed star domatic number of a graph, Discrete Applied Mathematics 158, pp. 213-218, 2010.
[2] S. Funke and C. Klein, Hole detection or: How much geometry hides in connectivity?, Proc. 22nd ACM Symposium on Computational Geometry, SoCG, pp. 377-385, 2006.
[3] S. Funke and N. Milosavljevic, Network sketching or: How much geometry hides in connectivity?-Part II, Proc. 18th ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 958-967, 2007.
[4] T. W. Haynes, S.T. Hedetniemi and P.J. Slater, Fundamentals of Domination in Graphs, Marcel Dekker, Inc., New York, 1998.
[5] M. A. Henning, On the signed total domatic number of a graph, Ars Combinatoria 79, pp. 277-288, 2006.
[6] B. Karp and H.T. Kung, GPSR: greedy perimeter stateless routing for wireless networks, Proc. 6th Annual International Conference on Mobile Computing and Networking, MobiCom, pp. 243-254, 2000.
[7] Y. Kim, R. Govindan, B. Karp and S. Shenker, Geographic routing made practical. Proc. 2nd Symposium on Networked System Design and Implementation, NSDI 2, pp. 217-230, 2005.
[8] E. Kranakis, H. Singh and J. Urrutia, Compass routing on geometric networks. Proc. 11th Canadian Conference on Computational Geometry, pp. 51-54, 1999.
[9] F. Kuhn, R. Wattenhofer and A. Zollinger, Worst-case optimal and average-case efficient geometric ad-hoc routing, Proc. 4th ACM International Symposium on Mobile Ad Hoc Networking and Computing, MobiHoc, pp. 267-278, 2003.
[10] D. Meierling, L. Volkmann and S. Zitzen, The signed domatic number of some regular graphs, Discrete Applied Mathematics 157, pp. 1905-1912, 2009.
[11] L. Volkmann, Signed domatic number of the complete bipartite graphs, Utilitas Mathematica 68, pp. 71-77, 2005.
[12] L. Volkmann, Some remarks on the signed domatic numbers of graphs with small minimum degree, Applied Mathematics Letters 22, pp. 1166-1169, 2009.
[13] L. Volkmann, Bounds on the signed domatic number, Applied Mathematics Letters 24, pp. 196-198, 2011.
[14] L. Volkmann and B. Zelinka, Signed domatic number of a graph, Discrete Applied Mathematics 150, pp. 261-267, 2005.
[15] C. Wang, The signed star domination numbers of the Cartesian product, Discrete Applied Mathematics 155, pp. 1497-1505, 2007.
[16] Y.Wang, J. Gao and J.S. Mitchell, Boundary recognition in sensor networks by topological methods, Proc. 12th Annual International Conference on Mobile Computing and Networking, MobiCom, pp. 122-133, 2006.
[17] D. B. West, Introduction to Graph Theory, Prentice-Hall, Inc., 2000.
[18] B. Xu, On signed edge domination numbers of graphs, Discrete Mathematics 239, pp. 179-189, 2001.
[19] B. Xu, On edge domination numbers of graphs, Discrete Mathematics 294, pp. 311-316, 2005.
[20] F. Zhang, A. Jiang and J. Chen, On the planarization of wireless sensor networks, Algorithmica 60, pp. 593-608, 2011.