請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/48605
完整後設資料紀錄
DC 欄位 | 值 | 語言 |
---|---|---|
dc.contributor.advisor | 呂育道(Yuh-Dauh Lyuu) | |
dc.contributor.author | Wei-Chih Huang | en |
dc.contributor.author | 黃韋誌 | zh_TW |
dc.date.accessioned | 2021-06-15T07:04:16Z | - |
dc.date.available | 2011-01-17 | |
dc.date.copyright | 2011-01-17 | |
dc.date.issued | 2010 | |
dc.date.submitted | 2010-12-28 | |
dc.identifier.citation | [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. | |
dc.identifier.uri | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/48605 | - |
dc.description.abstract | 假設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)。 | zh_TW |
dc.description.abstract | 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. | en |
dc.description.provenance | Made available in DSpace on 2021-06-15T07:04:16Z (GMT). No. of bitstreams: 1 ntu-99-R97922111-1.pdf: 433715 bytes, checksum: 6a04b4e5f5c994b42edae12273e37055 (MD5) Previous issue date: 2010 | en |
dc.description.tableofcontents | 致 謝 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 | |
dc.language.iso | zh-TW | |
dc.title | 在圍長為g之簡單有向圖上之動態壟斷 | zh_TW |
dc.title | Dynamic Monopoly in Simple Directed Graphs with Girth g | en |
dc.type | Thesis | |
dc.date.schoolyear | 99-1 | |
dc.description.degree | 碩士 | |
dc.contributor.oralexamcommittee | 張經略(Ching-Lueh Chang),狄彥吾(Yen-Wu Ti) | |
dc.subject.keyword | 演算法,圖論,動態壟斷, | zh_TW |
dc.subject.keyword | algorithm,graph theory,dynamic monopoly, | en |
dc.relation.page | 40 | |
dc.rights.note | 有償授權 | |
dc.date.accepted | 2010-12-29 | |
dc.contributor.author-college | 電機資訊學院 | zh_TW |
dc.contributor.author-dept | 資訊工程學研究所 | zh_TW |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf 目前未授權公開取用 | 423.55 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。