目標集選擇問題

On the target set selection problem

江俊瑩(Chun-ying Chiang)

指導教授 ： 葉鴻國

國立中央大學/理學院/數學系/博士(2012年)

摘要

在本篇論文裡，我們在不同的圖上考慮目標集選擇問題(target set selection problem)。
在第二章，我們證明了在任意閾值(thresholds)的區塊仙人掌圖(block-cactus graphs)以及閾值小於等於2的弦圖(chordal graph)上，目標集選擇問題可以在線性時間內解決。當考慮閾值為2的漢米圖(Hamming graphs)時，我們可以給出一個最佳解。在第三章，我們考慮的是閾值為2的cycle permutation graphs和廣義彼得森圖形。在第四章，對於閾值為3的torus cordalis 與torus serpentinus的最佳解，提出一個改進的上界。在第五章，我們考慮以下幾種蜂巢狀網路在strict majority thresholds下的目標集選擇問題：蜂巢式網格(honeycomb mesh)、蜂巢式環形曲面(honeycomb torus)、蜂巢式矩形環形曲面(honeycomb rectangular torus)、蜂巢式菱形環形曲面(honeycomb rhombic torus)、廣義蜂巢式環形曲面(generalized honeycomb torus)以及六角網格(hexagonal grids)。在第六章，我們研究多邊形拼圖在strict majority thresholds下的目標集選擇問題。

關鍵字

區塊仙人掌圖 ； 擴散 ； 社群網路 ； 目標集選擇 ； 六角網格 ； 弦圖 ； 漢米圖 ； 環面 ； 蜂巢狀網路

並列摘要

In this thesis, We are interested in the target set selection problem on different kinds of graphs.
In Chapter 2, we show that if G is a block-cactus graph with general thresholds, then the TARGET SET SELECTION problem can be solved in linear time. When G is a chordal graph with thresholds heta(v) leq 2 for each vertex v in G, then the problem can also be solved in linear time. We precisely determine an optimal target set for a Hamming graph G with constant threshold heta(v) = 2 for each vertex v in G.
In Chapter 3, we determine an optimal target set for (G,2) where G is a cycle permutation graph or a generalized Petersen graph.
In Chapter 4, we present some improved upper bounds and exact values for the parameters min-seed(C_m oslash C_n,3) and min-seed(C_m otimes C_n,3).
In Chapter 5, we study the TARGET SET SELECTION problem under strict majority thresholds on different kinds of honeycomb networks such as honeycomb mesh HM_t, honeycomb torus HT_t, honeycomb rectangular torus HReT(m,n), honeycomb rhombic torus HRoT(m,n), generalized honeycomb rectangular torus GHT(m,n,d) and three kinds of hexagonal grids (planar, cylindrical, and toroidal).
In Chapter 6, we determine minimum target sets for several tilings of the plane under strict majority threshold.

並列關鍵字

honeycomb networks ； chordal graph ； block-cactus graph ； diffusion ； social networks ； target set selection ； tori ； Hamming graph ； hexagonal grid

參考文獻

[26] D. Kempe, J. Kleinberg, E. Tardos, Maximizing the spread of in°uence through a

[1] E. Ackerman, O. Ben-Zwi, G. Wolfovitz, Combinatorial model and bounds for

target set selection, Theoretical Computer Science 411 (2010) 4017-4022.

[2] S. S. Adams, D. S. Troxell, S. L. Zinnen, Dynamic monopolies and feedback

62 (2011) 4049-4057.