文档介绍：Department of Mathematics
Fu Jen Catholic University
Combinatorial Optimization
Dr. Justie Su-tzu Juan
Lecture 3. Domination Problem in Tree
Slides for a Course
(c) Spring 2007, Justie Su-tzu Juan 1
Domination Problem in Tree
Def: A dominating set of a graph G = (V, E) is a subset D of V such
that x V –D, y D with xy E.
Ex. x4 y1
Let D = {y , y }, D = {x , y , x },
x x 1 1 2 2 1 2 4
3 C6 1
then D1, D2 are dominating sets of C6.
y2 x2
Notation: domination number of G (G) = min{|D| : D is a
dominating set of G}.
The Minimum Dominating Set Problem in general graph G is NP-
complete.
(c) Spring 2007, Justie Su-tzu Juan 2
Department of Mathematics
Fu Jen Catholic University
Combinatorial Optimization
Dr. Justie Su-tzu Juan
Lecture 3. Domination Problem in Tree
§ Method 1 : L-dominating
Slides for a Course Based on the Paper
E. J. Cockayne, S. E. Goodman and S. T. Hedetniemi,
“A linear algorithm for the domination number of a
tree”, Inform. Process. Lett. 4 (1975), 41-44.
(c) Spring 2007, Justie Su-tzu Juan 3
Method 1: L-dominating
Note :
Suppose D is an optimal dominating set of tree T.
x: a leaf, adjacent to vertex y :
y D x D
T (. D–{x} is also a dominating set with |D–{x}| |D| )
y
y D x D
x
let D= (D–{x}){y} is also a dominating set as N[x] N[y]
So, always an optimal dominating set D such that y D and x D,
for any leaf x adjacent to vertex y
Step 1: 配合“bound”vertex N[y] B BR
Step 2: 產生“free”vertex x F
Step 3: 再產生“required”vertex y R BF
(c) Spring 2007, Justie Su-tzu Juan 4
Method 1: L-dominating
Def: G = (V, E) is a graph, L : V {B, R, F}, (., each vertex x has a
label L(x) {B, R, F}.)
An L-dominating (mixed dominating) set of G is a subset D V(G)
. L(x) = R x D
L(x) = B N[x] D
Notation: (G, L) = min{|D| : D is a L-dominating set of G}.
Ex: G G G G
1 B 2 F 3 R 4 R
B B B B
B B F F F F