Logo image
A Survey on Broadcast Domination Problem
Thesis

A Survey on Broadcast Domination Problem

Lu, Shao-chia
Masters, 國立清華大學, 資訊工程學系
2008

Abstract

演算法 圖形 支配 廣播支配 Algorithms Graph Domination Broadcast Domination
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_{v\in 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.

Metrics

1 Record Views

Details

Logo image