崩壞點模型相關演算法之去隨機化研究

Derandomizing algorithms for perfect target set selection

陳彥良(Yan-Liang Chen)

指導教授 ： 張經略

元智大學/資訊學院/資訊工程學系/碩士(2012年)

https://doi.org/10.6838/YZU.2012.00304

摘要

在這篇論文裡，假設G(V,E)是一個簡單無向圖，G上的所有節點只有兩狀態：開啟或關閉，一開始有一個節點集合S，在集合S中的節點(我們稱作啟動點)都是開啟的，其餘的節點都是關閉的，當一個關閉節點的鄰近節點超過α比例是開啟的，此關閉的節點就會被開啟，整個過程會一直進行到沒有更多節點可以被開啟為止。如果G上所有節點最終都被開啟，我們將S這個集合稱為α perfect target set簡稱為α"-" PTS。Chang [6]提出了一個多項式時間的隨機演算法可以在任何無向連通圖中，找出一個大小的期望值不超過(2√2+3)⌈α|V|⌉的α"-" PTS，我們要處理的問題就是使用條件期望值的方法將Chang的隨機演算法去隨機化，因此我們的確定性(deterministic)多項式時間演算法能在任何無向連通圖中找到大小不超過(2√2+3)⌈α|V|⌉的α"-" PTS。

關鍵字

啟動點 ； 條件期望值 ； 去隨機化 ； 確定性多項式時間演算法

並列摘要

In this paper, let G(V,E) be a simple undirected graph, with only two possible states for each vertex: Active or inactive. Only a set S of vertices are activated initially. Thereafter, an inactive vertex is activated when at least α fraction of its neighbors are active. The process will continue until no more vertices can be active. If all vertices are activated before the process ends, we call S an α perfect target set, abbreviated as α perfect target set. Chang [6] proposed a polynomial time randomized algorithm which, given any connected undirected graph, finds an α"-" PTS whose expected size does not exceed (2√2+3)⌈α|V|⌉. We use the method of conditional expectation to derandomize the algorithm of Chang. Therefore, our deterministic polynomial time algorithm can find an α"-" PTS of size no more than (2√2+3)⌈α|V|⌉ in any undirected connected graph.

並列關鍵字

Active ； Conditional expectation ； Derandomize ； Deterministic polynomial time algorithm

參考文獻

[1] E. Ackerman, O. Ben-Zwi, and G. Wolfovitz. Combinatorial model and bounds for target set selection. Theoretical Computer Science, 411(44–46):4017–4022, 2010.

[2] S. S. Adams, D. S. Troxell, and S. L. Zinnen. Dynamic monopolies and feedback vertex sets in hexagonal grids. Computers and Mathematics with Applications, 62(11):4049–4057, 2011.

[3] E. Berger. Dynamic monopolies of constant size. Journal of Combinatorial Theory Series B, 83(2):191–200, 2001.

[4] C.-L. Chang and Y.-D. Lyuu. Spreading messages. Theoretical Computer

[6] C.-L. Chang. Triggering cascades on undirected connected graphs. Information Processing Letters, pp. 111(19):973-978,2011