Information Technology Reference
In-Depth Information
Figure 10.3 The pyramid graph on six inputs.
1 . There exists a pebbling strategy that pebbles P ( m ) with m pebbles using one pebble placement
per vertex.
Proof The lower-bound proof again uses the fact that there is a first time at which all paths
from an input to the output carry pebbles. Highlighted in Fig. 10.3 is a last path to carry
a pebble. Prior to the placement of this last pebble, all paths to the output carry pebbles.
Thus, with the placement of the last pebble there must be at least as many pebbles on the
pyrami d gr aph as there are vertices on a path from an input to the output, namely, m ,and
m
2 n
1. (See Problem 10.1 .)
With m pebbles, the vertices can be pebbled in levels by first placing pebbles on each of
the m inputs. Pebbles are then advanced to vertices on the second level from left to right,
and this process is repeated at all levels to complete the pebbling. Each vertex is pebbled
once with this strategy.
In general, it is very hard to determine the minimum number of pebbles needed to pebble
a graph. In terms of the complexity classes introduced in Chapter 8 , we model this problem as
a language consisting of strings each of which contains the description of a graph G =( V , E ) ,
avertex v
V ,andaninteger S with the property that the vertex can be pebbled with S or
fewer pebbles. The language of these strings is PSPACE -complete (see Section 8.12 ).
10.3 Extreme Tradeoffs
We now show that extreme space-time tradeoff behavior is possible. We do this by exhibiting a
family of graphs, H 1 , H 2 , ... , H k , ... (Fig. 10.4 ), that requires a number of steps exponential
in the size of the graph when the minimum number of pebbles is used but only one step per
vertex when one more pebble is available. This illustrates that excessive minimization of the
number of registers used by programs can be harmful!
H 1 has one input and one output vertex and an edge connecting them, as shown in
Fig. 10.4 .For k
2the k th graph, H k ,has k + 1 output vertices and is constructed from
one copy of H k− 1 ,atree(ontheleft)with k inputs, a two-level bipartite graph (on the top
right) with k inputs and k + 1outputs,andachainof k vertices that connects the tree to the
outputs of H k− 1 and the open vertex. (A bipartite graph is a graph in which the vertices are
partitioned into two sets and edges join vertices in different sets.)
We summarize our pebbling results for this family of graphs below. Here n ! is the factorial
function with value n != n
·
( n
1 )
·
( n
2 )
·
...
·
2
·
1.
Search WWH ::




Custom Search