廣播支配問題之研究

A Survey on Broadcast Domination Problem

呂紹甲(Shao-chia Lu)

指導教授 ： 唐傳義

國立清華大學/電機資訊學院/資訊工程學系/碩士(2009年)

https://doi.org/10.6843/NTHU.2009.00047

摘要

所謂圖形上的廣播支配是找出一個函數讓此圖形上的每個點都對應到一個大於等於零的整數使得這個函數滿足對於圖形上的每個點，至少都有一個值大於零的點跟它的距離是在這個值之間。而圖形上的廣播支配問題則是在該圖形上找出一個符合廣播支配的函數，使得每個點所對應的值加起來之總和是最小的。在這篇論文中，我們針對廣播支配問題做一個綜述以及提出一些和半徑樹(廣播支配函數對應值的總和為半徑長的樹)有關的特徵描述。

關鍵字

演算法 ； 圖形 ； 支配 ； 廣播支配

並列摘要

A broadcast domination function on a graph $G=(V,E)$ is a function $f$ that maps $V$ into ${0,1,dots,k}$ such that every vertex of $G$ within distance $f(v)$ from some vertex $v$ with $f(v)>0$. The cost of a broadcast domination function $f$ is $Sigma_{vin V}f(v)$. The broadcast domination problem on $G$ is to find a minimum cost broadcast domination function on $G$.
In this thesis, we present an overview of the broadcast domination problem and some results on characterizations of radial trees.

並列關鍵字

Algorithms ； Graph ； Domination ； Broadcast Domination

參考文獻

algorithms for interval graphs, series-parallel graphs, and trees, Congr. Numer.

169 (2004), pp. 55–77.

[3] K.S. Booth, J.H. Johnson, Dominating sets in chordal graphs, SIAM J. Com-

on Discrete Mathematics and Applications, Philadelphia, 1999.

[7] M.-S. Chang, Efficient algorithms for the domination problems on interval and