Information Technology Reference
In-Depth Information
Any pebbling strategy will need to use at least as many pebbles as this minimum value of space.
It can be shown that no bounded-degree graph on
n
vertices requires more than
O
(
n/
log
n
)
space (see Theorem
10.7.1
) and that some graph requires space proportional to
n/
log
n
(see
Theorem
10.8.1
).
Complete balanced binary trees were introduced in the previous section. We now derive a
lower bound on the space (number of pebbles) needed to pebble them.
LEMMA
10.2.1
Any pebbling strategy for the complete balanced binary tree of depth
k
,
T
(
k
)
,
requires at least
S
min
(
T
(
k
)) =
k
+
1
pebbles and
2
k
+
1
−
1
steps. There is a pebbling strategy of
T
(
k
)
that uses exactly this many pebbles and steps.
Proof
Proof of the lemma requires a proof that
k
+
1 pebbles are necessary as well as a
strategy that pebbles the tree with
k
+
1 pebbles and makes one pebble placement per
vertex. Let's first develop a pebbling strategy.
T
(
0
)
obviously can be pebbled with one pebble in one step. Assume that
T
(
k
−
1
)
can
be pebbled with
k
pebbles in 2
k
−
1 steps. To pebble
T
(
k
)
, advance a pebble to the root of
its left subtree (a copy of
T
(
k
−
1
)
)using
k
pebbles and 2
k
−
1 steps. Leave a pebble on its
root. Then pebble the right subtree of
T
(
k
)
using
k
pebbles and 2
k
−
1 steps. (A snapshot
of
T
(
k
)
when the number of pebbles is maximal under this pebbling strategy is shown in
Fig.
10.2
.) Thus,
T
(
k
)
is pebbled in 2
(
2
k
1
)+
1
=
2
k
+
1
1stepswith
k
+
1 pebbles.
The lower bound is derived by showing that no pebbling strategy can use fewer than
k
+
1 pebbles. The argument used is the following: initially no path to the root of the tree
(or output) from input vertices carries a pebble because there are no pebbles on the graph.
At the end of the computation a pebble resides on the root and all paths to the root carry
pebbles. Therefore, there must be a first point in time at which there is a pebble on each
path to the root. This must be a time at which a pebble is placed on an input vertex, thereby
closing the last path from that input to the root. Such a path is highlighted in Fig.
10.2
.
Before a pebble is placed on the input vertex of this path, all other paths from input vertices
to the root carry pebbles. Each of these paths enters the highlighted path via one edge. Thus,
it follows that prior to the placement of this last pebble there is at least one pebble on the
tree for each of the
k
edges on this path except for the input vertex. Consequently, at least
k
+
1 pebbles are on the tree when the last pebble is placed on it.
×
−
−
The FFT graph on 2
k
inputs,
F
(
k
)
, is defined recursively in terms of two sub-FFT graphs
F
(
k−
1
)
as shown in Section
6.7.2
. It follows that this graph contains many copies of the tree
T
(
k
)
as a subgraph (see Problem
10.11
) and that any pebbling strategy for
F
(
k
)
requires at
least
k
+
1 pebbles. Many other straight-line computations involve tree computations.
A
pyramid graph
on
m
inputs,
P
(
m
)
(
P
(
6
)
is shown in Fig.
10.3
), is obtained by slicing
an
m
m
mesh into two parts along its diagonal, splitting all diagonal nodes (which are now
inputs), and then directing edges from the diagonal vertices in one part to the one remaining
unsplit corner vertex in this part of the graph. Edges are directed up, a convention we use
throughout this chapter.
P
(
m
)
has
n
=
m
(
m
+
1
)
/
2 vertices. (See Problem
10.1
.)
We apply to the pyramid graph
P
(
m
)
the lower bounding argument used in the preceding
proof based on closing the last open path to the output vertex.
×
LEMMA
10.2.2
Anypebblingstrategyforthe
m
-input,
n
-vertex (
n
=
m
(
m
+
1
)
/
2
)pyramid
graph
P
(
m
)
requires at least
m
pebbles; that is, a minimum space
S
min
(
P
(
m
)) =
m
√
2
n
≥
−
Search WWH ::
Custom Search