博碩士論文 101221023 詳細資訊




以作者查詢圖書館館藏 以作者查詢臺灣博碩士 以作者查詢全國書目 勘誤回報 、線上人數:11 、訪客IP:54.91.4.56
姓名 郭瀚文(Han-wun Guo)  查詢紙本館藏   畢業系所 數學系
論文名稱 路徑圖與格子圖上的目標集問題
(Target Set Selection Problem on Paths and Grids)
相關論文
★ 圓環面網路上的病毒散播★ 以2D HP 模型對蛋白質摺疊問題之研究
★ On Steiner centers of graphs★ On the Steiner medians of a block graph
★ 圖形列表著色★ 秩為5的圖形
★ Some results on distance-two labeling of a graph★ 關於非奇異線圖的樹
★ On Minimum Strictly Fundamental Cycle Basis★ 目標集選擇問題
★ 超立方體圖與格子圖上的目標集問題★ 圖形環著色數的若干等價定義
★ 網格圖上有效電阻計算方法的比較★ d 維立方體圖上有效電阻與首達時間的計算方法
檔案 [Endnote RIS 格式]    [Bibtex 格式]    [相關文章]   [文章引用]   [完整記錄]   [館藏目錄]   [檢視]  [下載]
  1. 本電子論文使用權限為同意立即開放。
  2. 已達開放權限電子全文僅授權使用者為學術研究之目的,進行個人非營利性質之檢索、閱讀、列印。
  3. 請遵守中華民國著作權法之相關規定,切勿任意重製、散佈、改作、轉貼、播送,以免觸法。

摘要(中) 本論文主要在處理路徑圖 (Path) 上的 Target set Selection Problem (TSS Problem),另外對 Pn□Pm 圖上也得到一些結果。我們在 TSS Problem 上考慮兩類感染方式:並行感染規則 I 與並行感染規則 II。
在並行感染規則 I 下,將已有的 Theorem 1 至 Theorem 3 ([3], [6]) 從 Pn□Pn 推廣到 Pn□Pm,並給出不等式等號成立的充分條件。在並行感染規則 II 下,討論並行感染規則 II 的性質 (遞增性,圖形與子圖的關係),在圖形為 path 時,討論 min-seed 在子圖中的下界,對於在 path 上一般性的情形,其中 a_i?2 的情形可以得到結果,一般性的情形 a_i?0 還沒有解決,但可以推論出問題的關鍵在於? a?_i?1 的情形。
摘要(英) In this paper, we are focus on the Target set Selection Problem (TSS Problem) on path. We also get some results on Pn□Pm. Consider two different rules of Bootstrap Percolation:
Rule I and Rule II
Under Rule I, we generalize Theorem 1, Theorem 2 and Theorem 3 ([3], [6]) from Pn□Pn
to Pn□Pm.. Furthermore, we give some sufficient conditions for inequality such that equality holds. On the other hand, we have some properties under Rule II and results on path.
關鍵字(中) ★ 路徑圖
★ 格子圖
★ 目標集問題
關鍵字(英) ★ path
★ grids
★ TTS
★ Target set
論文目次 1 Introduction 1
2 Examples for TSS Problem 3
3 TSS Problem on Path 10
References 16
參考文獻 [1] E. Ackerman, O. Ben-Zwi, and G. Wolfovitz, Combinatorial model and bounds for
target set selection, Theoret. Comput. Sci., 411(2010), pp. 4017-4022.
[2] S. S. Adams, D. S. Troxell, and S. L. Zinnen, Dynamic monopolies and feedback
vertex sets in hexagonal grids, Comput. and Math. Appl., 62(2011), pp. 4049-4057.
[3] Bela Bollobas, The Art of Mathematics Coffee Time in Memphis, Cambridge University Pressm, 2006, pp. 171-172.
[4] E. Berger, Dynamic monopolies of constant size, J. Combin. Theory Ser. B, 83(2001),
pp. 191-200.
[5] O. Ben-Zwi, D. Hermelin, D. Lokshtanov, and I. Newman, Treewidth governs the
complexity of target set selection, Discrete Optim., 8(2011), pp. 87-96.
[6] J. Balogh and G. Pete, in Proceedings of the Eighth International Conference ′Random
Structures and Algorithms′ (Poznan, 1997), Random Structures Algorithms, 13(1998) pp. 409-422.
[7] N. Chen, On the approximability of influence in social networks, SIAM J. Discrete
Math., 23(2009), pp. 1400-1415.
[8] C. -Y. Chaing, L. -H. Huang, B. -J. Li, J. Wu, and H. -G. Yeh, Some Results on the
Target Set Selection Problem, J. Comb. Optim., to appear.
[9] P. A. Dreyer and F. S. Roberts, Irreversible k-threshold processes: Graph-theoretical
threshold models of the spread of disease and of opinion, Discrete Applied Math.,
157(2009), pp. 1615-1627.
[10] P. Flocchini, F. Geurts, and N. Santoro, Optimal irreversible dynamos in chordal rings, Discrete Appl. Math., 113(2001), pp. 23-42.
[11] P. Flocchini, R. Kralovi?, P. Ru?i?ka, A. Roncato, and N. Santoro, On time versus
size for monotone dynamic monopolies in regular topologies, J. Discrete Algorithms,
1(2003), pp. 129-150.
[12] P. Flocchini, E. Lodi, F. Luccio, L. Pagli, and N. Santoro, Dynamic monopolies in tori, Discrete Appl. Math., 137(2004), pp. 197-212.
[13] P. Flocchini, Contamination and Decontamination in Majority-Based Systems, J. Cell.
Autom., 4(2009), pp. 183-200.
[14] D. Kempe, J. Kleinberg, and E. 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.
[15] D. Kempe, J. Kleinberg, and E. Tardos, Influential nodes in a diffusion model for
social networks, in Proceedings of the 32th International Colloquium on Automata,
Languages and Programming, 2005, pp. 1127-1138.
[16] F. Luccio, Almost exact minimum feedback vertex set in meshes and butterflies, Inform. Process. Lett., 66(1998), pp. 59-64.
[17] F. Luccio, L. Pagle, and H. Sanossian, Irreversible dynamos in butterflies, in proceedings of the 6th International Colloquium on Structural Information and Communication Complexity (SIROCCO), 1999, pp. 204-218.
[18] D. Peleg, Size bounds for dynamic monopolies, Discrete Appl. Math., 86(1998) pp.
263-273.
[19] D. Peleg, Local majorities, coalitions and monopokies in graphs: A review, Theoret.
Comput. Science, 282(2002) pp. 231-257.
[20] D. A. Pike and Y. Zou, Decycling Cartesian products of two cycles, SIAM J. Discrete
Math., 19(2005) pp. 651-663.
[21] M. Zaker, On dynamic monopolies of graphs with general thresholds, Discrete Math.,
312(2012) pp. 1136-1143.
指導教授 葉鴻國(Hong-Gwa Yeh) 審核日期 2014-6-30
推文 facebook   plurk   twitter   funp   google   live   udn   HD   myshare   reddit   netvibes   friend   youpush   delicious   baidu   
網路書籤 Google bookmarks   del.icio.us   hemidemi   myshare   

若有論文相關問題,請聯絡國立中央大學圖書館推廣服務組 TEL:(03)422-7151轉57407,或E-mail聯絡  - 隱私權政策聲明