Information Technology Reference
In-Depth Information
k
+
1
3
k
k
H
1
H
k−
1
k
H
1
H
2
H
k
Figure 10.4
A family of graphs exhibiting an extreme tradeoff.
THEOREM
10.3.1
The graph
H
k
has
N
(
k
)=
2
k
2
+
5
k −
6
verti
ces for
k ≥
2
. Any pebbling
strategy for the graph
H
k
requires at least
k
pebbles,
k
=Θ
(
N
(
k
))
. Any strategy to pebble
H
k
with
k
pebbles requires at least
(
k
+
1
)!
/
2
=
2
Ω
√
N
(
k
)log
N
(
k
)
steps, whereas there exists a
pebbling algorithm using
k
+
1
pebbles that pebbles each vertex of
H
k
once.
Proof
Consider a pebbling strategy that uses
k
+
1 pebbles to pebble
H
k
.Forthecaseof
k
=
1,
H
k
can be completely pebbled with one move per vertex. This is also true for
H
2
because we can move a pebble to the open vertex connected to the bipartite graph using two
pebbles, from which we can advance two of our three pebbles to the bottom layer of the
bipartite graph and have one additional pebble with which to pebble the output vertices.
Note that this pebbling strategy allows us to pebble output vertices of
H
2
from left to right
with three pebbles.
Assume that we can pebble the outputs of
H
k−
1
from left to right with
k
pebbles without
pebbling any vertex more than once. Then to pebble
H
k
, advance a pebble to the root of
the tree on the left and then pebble the outputs of
H
k−
1
from left to right using
k
pebbles
while keeping one additional pebble on the chain. Advance this pebble along the chain until
it reaches the open vertex. At this point
k
pebbles can be advanced to the bottom row of
vertices in the bipartite graph and the remaining pebble used to pebble outputs from left to
right. This shows that our assumption holds.
The minimum number of pebbles needed to pebble
H
k
is at least
k
because at least this
many are needed to pebble the tree on the left. To show that this value can be achieved, we
give a recursive pebbling strategy. Observe that
H
1
can be pebbled with
k
=
1 pebbles. To
pebble
H
k
, assume that we can pebble any one output of
H
k−
1
with
k
1 pebbles. Advance
a pebble to the root of the left tree and then advance it along the chain by pebbling output
vertices of
H
k−
1
from left to right with
k
−
1 pebbles. Move a pebble to the open vertex
and then to all vertices on one side of the bipartite graph. Any one output vertex can now
be pebbled. However, doing so requires that one vertex on the bottom side of the bipartite
graph lose its pebble. Thus, no other output vertex can be pebbled without repebbling the
tree and all vertices of
H
k−
1
.
−
Search WWH ::
Custom Search