Information Technology Reference
In-Depth Information
marked children of
u
.Notethat
W
(
v
)and
W
(
v
)aredisjointfor
v,v
∈
T
\
R
with
v
=
v
.Wehave
=
n.
(1)
Let
L
t
and
I
t
be the set of marked vertices of
v∈X
t
W
(
v
) that are leaves and
internal vertices in
T
, respectively, for
t
=
a,b,c,d
.Wehave
|
X
a
|
+
|
X
b
|
+
|
X
c
|
+
|
X
d
|
+
|
R
|
|
I
a
|
+
|
L
a
|
=6
|
X
a
|
|
L
a
|≤
3
|
X
a
|
(2)
|
I
b
|
+
|
L
b
|
=5
|
X
b
|
|
L
b
|
=0
(3)
|
I
c
|
+
|
L
c
|
=5
|
X
c
|
|
L
c
|≤
2
|
X
c
|
(4)
|
I
d
|
+
|
L
d
|
=4
|
X
d
|
|
L
d
|
=0
(5)
Since
R
always contains all leaves of
T
,wehave
|
R
|≥
c
0
+
|
I
a
|
+
|
I
b
|
+
|
I
c
|
+
|
I
d
|
,
(6)
where
c
i
is the number of vertices with exactly
i
children in
T
.Notethat
W
(
v
)
contains a vertex with at least three children if
v
∈
X
a
∪
X
b
∪
X
d
. Hence, by
Lemma 2,
c
1
+
n−
1
c
0
>
n
−
i
=3
c
i
n
−
c
1
+
|
X
a
|
+
|
X
b
|
+
|
X
d
|
≥
.
(7)
2
2
In addition, we have
c
0
≥|
L
a
|
+
|
L
b
|
+
|
L
c
|
+
|
L
d
|
.
(8)
Before we bound
, consider the set
S
formed by all leaves and all vertices with
one child. Then
S
is column planar by Lemma 1 and
|
R
|
=
c
0
+
c
1
. Whenever
the greedily chosen
R
hassizelessthan
c
0
+
c
1
,wechoose
R
=
S
instead. Thus,
we may assume
|
S
|
|
R
|≥
c
0
+
c
1
.
(9)
Equations (7) and (9) yield
|
R
|
>n
−
c
0
+
|
X
a
|
+
|
X
b
|
+
|
X
d
|
;
(10)
equations (2) and (8) yield
c
0
≥
6
|
X
a
|−|
I
a
|
+
|
L
c
|
;
(11)
and equations (3), (4), (5), and (6) yield
|
R
|≥
c
0
+5
|
X
b
|
+5
|
X
c
|
+4
|
X
d
|−|
L
c
|
+
|
I
a
|
.
(12)
To eliminate
c
0
, we combine equation(10) with two times (11) and three times (12)
to obtain 4
|
R
|
>n
+13
|
X
a
|
+16
|
X
b
|
+15
|
X
c
|
+13
|
X
d
|−|
L
c
|
+
|
I
a
|
. With
equation (4), this gives 4
|
R
|
>n
+13
|
X
a
|
+16
|
X
b
|
+13
|
X
c
|
+13
|
X
d
|
+
|
I
a
|≥
n
+13(
|
X
a
|
+
|
X
b
|
+
|
X
c
|
+
|
X
d
|
). Together with equation (1), this yields the desired
bound of
|
R
|
>
14
n/
17.
