目標集選擇問題;On the target set selection problem

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/54311

Title:	目標集選擇問題;On the target set selection problem
Authors:	江俊瑩;Chiang,Chun-ying
Contributors:	數學研究所
Keywords:	區塊仙人掌圖;擴散;社群網路;目標集選擇;六角網格;弦圖;漢米圖;環面;蜂巢狀網路;honeycomb networks;chordal graph;block-cactus graph;diffusion;social networks;target set selection;tori;Hamming graph;hexagonal grid
Date:	2012-06-28
Issue Date:	2012-09-11 18:44:13 (UTC+8)
Publisher:	國立中央大學
Abstract:	在本篇論文裡，我們在不同的圖上考慮目標集選擇問題(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.
Appears in Collections:	[Graduate Institute of Mathematics] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	572	View/Open

社群 sharing

Loading...