臺灣博碩士論文加值系統

假設G(V,E)為一簡單有向圖（simple directed graph），意即圖中任兩點（vertex）之間最多只存在一條邊（edge），每一條邊皆有一個方向。若G(V,E)之最短迴圈之長度為 ，則稱G(V,E)之圍長（girth）為g。此外，我們額外限制在簡單有向圖上每一點皆至少有一個內鄰（in-neighbor）。考慮以下有向圖上的擴散過程：最初，一些圖上的點處於已啟動（active）狀態，這些初始化為已啟動的點稱之為種子（seed）；而其他點則為未啟動（inactive）狀態。當一個未啟動的點有過半的內鄰為已啟動狀態時，則該點亦會被啟動（activated）。而依此規則，擴散過程將持續至沒有其他未啟動的點可被啟動為止，此過程即為動態壟斷。在動態壟斷（dynamic monopoly）問題之中，我們注重的是：在擴散過程中，可以啟動所有點的種子集合。而本論文推導出在圍長為g之簡單有向圖G(V,E)中，最小可啟動所有點的種子集合之大小上限為 floor(|V|/2)+ceiling(|V|/2g)。

Suppose G(V,E) is a simple directed graph, where there is at most one directed edge between each pair of vertices. We say G(V,E) has girth g if the length of the shortest cycle in is . We shall require that each vertex in a simple directed graph have at least one in-neighbor. Now, consider a process of propagations in a directed graph G(V,E) as follows. Some vertices, called seeds, in V are initially active, and the others are inactive. Later, an inactive vertex is activated if over half of its in-neighbors are active, and such activations end while no more vertices can be activated. In dynamic monopoly problems, we focus on such a set of seeds in V that all vertices will be activated at the end of propagations. In this thesis, we derive an upper bound, floor(|V|/2)+ceiling(|V|/2g), on size of such a set of seeds for any simple directed graph G(V,E) with girth g.

致 謝 i
摘 要 ii
Abstract iii
圖目錄 vi
第一章 緒論 1
1.1 研究目的 1
1.2 論文背景 1
1.3 論文貢獻 3
1.4 論文架構 4
第二章 圖論用語與動態壟斷之擴散過程介紹 5
2.1 圖論用語與符號介紹 5
2.2 動態壟斷之擴散過程 6
第三章 最小重點種子集大小之上限 8
3.1 動態壟斷在圍長為 之簡單有向圖上之特性 8
3.2 證明最小重點種子集大小之上限 12
第四章 重點種子集之挑選 18
4.1 概述 18
4.2 模擬動態壟斷之擴散過程 19
4.3 尋找不平衡點 23
4.4 剩餘點組成之迴圈內之點 25
4.5 尋找重點種子集 28
4.6 複雜度分析 31
第五章 結論 35
參考文獻 36

[1]Eyal Ackerman, Oren Ben-Zwi, and Guy Wolfovitz. Combinatorial Model and Bounds for Target Set Selection. Theoretical Computer Science, 2010.
[2]H. Attiya and J. Welch. Distributed Computing: Fundamentals, Simulations and Advanced Topics. Hoboken, NJ: John Wiley & Sons, 2004.
[3]B. Awerbuch and C. Scheideler. Towards a scalable and robust DHT. Theory of Computing Systems, 45(2):234–260, 2009.
[4]Y. Azar, S. Kutten, and B. Patt-Shamir. Distributed error confinement. In Proceedings of the 22nd Symposium on Principles of Distributed Computing, 2003, pp. 33–42.
[5]Y. Birk, L. Liss, A. Schuster, and R. Wolff. A local algorithm for ad hoc majority voting via charge fusion. In Proceedings of the 18th International Symposium on Distributed Computing, 2004, pp. 275–289.
[6]D. M. Blough, G. F. Sullivan, and G. M. Masson. Efficient diagnosis of multiprocessor systems under probabilistic models. IEEE Transactions on Computers, 41(9):1126–1136, 1992.
[7]G. Bracha. An expected rounds randomized Byzantine generals protocol. Journal of the Association for Computing Machinery, 34(4):910–920, 1987.
[8]C.-L. Chang and Y.-D. Lyuu. On irreversible dynamic monopolies in general graphs. The Computing Research Repository, (abs/0904.2306), 2009.
[9]S. B. Davidson, H. Garcia-Molina, and D. Skeen. Consistency in a partitioned network: a survey. ACM Computing Surveys, 17(3):341–370, 1985.
[10]K. Diks and A. Pelc. System diagnosis with smallest risk of error. Theoretical Computer Science, 203(1):163–173, 1998.

[11]D. Dolev. The Byzantine generals strike again. Journal of Algorithms, 3(1):14–30, 1982.
[12]C. Dwork, D. Peleg, N. Pippenger, and E. Upfal. Fault tolerance in　networks of bounded degree. SIAM Journal on Computing, 17(5):975–988, 1988.
[13]P. Flocchini, F. Geurts, and N. Santoro. Optimal irreversible dynamos in chordal rings. Discrete Applied Mathematics, 113(1):23–42, 2001.
[14]P. Flocchini, R. Královič, P. Ružička, A. Roncato, and N. Santoro. On time versus size for monotone dynamic monopolies in regular topologies. Journal of Discrete Algorithms, 1(2):129–150, 2003.
[15] P. Flocchini, E. Lodi, F. Luccio, L. Pagli, and N. Santoro. Dynamic monopolies in tori. Discrete Applied Mathematics, 137(2):197–212, 2004.
[16]H. Garcia-Molina and D. Barbara. How to assign votes in a distributed system. Journal of the Association for Computing Machinery, 32(4):841–860, 1985.
[17]D. K. Gifford. Weighted voting for replicated data. In Proceedings of the 7th ACM Symposium on Operating Systems Principles, 1979, pp. 150–162.
[18]T. J. Harris. A survey of PRAM simulation techniques. ACM Computing Surveys, 26(2):187–206, 1994.
[19]M. Herlihy. A quorum-consensus replication method for abstract data types. ACM Transactions on Computer Systems, 4(1):32–53, 1986.
[20]D. Kempe, J. Kleinberg, and É. Tardos. Maximizing the spread of influence through a social network. In Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 2003, pp. 137–146.
[21]D. Kempe, J. Kleinberg, and É. Tardos. Influential nodes in a diffusion model for social networks. In Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, 2005, pp. 1127–1138.
[22]S. Kutten and D. Peleg. Fault-local distributed mending. Journal of Algorithms, 30(1):144–165, 1999.
[23]S. Kutten and D. Peleg. Tight fault locality. SIAM Journal on Computing, 30(1):247–268, 2000.
[24]J. Kynčl, B. Lidický, and T. Vyskočil. Irreversible 2-conversion set is NP-complete. Technical Report KAM-DIMATIA Series 2009-933, Department of Applied Mathematics, Charles University, Prague, Czech Republic, 2009.
[25]L. Lamport, R. Shostak, and M. Pease. The Byzantine generals problem. ACM Transactions on Programming Languages and Systems, 4(3):382–401, 1982.
[26]S. Lee and K. G. Shin. Probabilistic diagnosis of multiprocessor systems. ACM Computing Surveys, 26(1):121–139, 1994.
[27]F. Luccio, L. Pagli, and H. Sanossian. Irreversible dynamos in butterflies. In Proceedings of the 6th International Colloquium on Structural Information & Communication Complexity, 1999, pp. 204–218.
[28]N. A. Lynch. Distributed Algorithms. San Fransisco, CA: Morgan Kaufmann, 1996.
[29]E. Mossel and S. Roch. On the submodularity of influence in social networks. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007, pp. 128–134.
[30]M. Naor and A. Wool. The load, capacity, and availability of quorum systems. SIAM Journal on Computing, 27(2):423–447, 1998.
[31]A. Pelc. Efficient fault location with small risk. In Proceedings of the 3rd Colloquium on Structural Information and Communication Complexity, 1996, pp. 292–300.
[32]D. Peleg and A. Wool. The availability of quorum systems. Information and Computation, 123(2):210–223, 1995.
[33]A. Pietracaprina and G. Pucci. The complexity of deterministic PRAM simulation on distributed memory machines. Theory of Computing Systems, 30(3):231–247, 1997.
[34]A. Pietracaprina, G. Pucci, and J. F. Sibeyn. Constructive deterministic PRAM simulation on a mesh-connected computer. In Proceedings of the 6th Annual ACM Symposium on Parallel Algorithms and Architectures, 1994, pp. 248–256.
[35]D. A. Pike and Y. Zou. Decycling Cartesian products of two cycles. SIAM Journal on Discrete Mathematics, 19(3):651–663, 2005.
[36]M. Raynal. Algorithms for mutual exclusion. Cambridge, MA: MIT Press, 1986.
[37]T. C. Schelling. Hockey helmets, concealed weapons, and daylight saving: a study of binary choices with externalities. Journal of Conflict Resolution, 17(3):381–428, 1973.
[38]M. Spasojevic and P. Berman. Voting as the optimal static pessimistic scheme for managing replicated data. IEEE Transactions on Parallel and Distributed Systems, 5(1):64–73, 1994.
[39]G. F. Sullivan. The Complexity of System-Level Fault Diagnosis and Diagnosability. Ph.D. thesis, Department of Computer Science, Yale University, 1986.
[40]R. H. Thomas. A majority consensus approach to concurrency control for multiple copy databases. ACM Transactions on Database Systems, 4(2):180–209, 1979.
[41]E. Upfal. Tolerating a linear number of faults in networks of bounded degree. Information and Computation, 115(2):312–320, 1994.
[42]E. Upfal and A. Wigderson. How to share memory in a distributed system. Journal of the ACM, 34(1):116–127, 1987.
[43]J. von Neumann. Probabilistic logics and synthesis of reliable organisms from unreliable components. In C. Shannon and J. McCarthy, editors, Automata Studies, 1956, pp. 43–98.
[44]D. J. Watts. A simple model of global cascades on random networks. Proceedings of the National Academy of Sciences, 99(9):5766–5771, 2002.