Information Technology Reference
In-Depth Information
SPACE LOWER BOUNDS WITH PEBBLING
10.11 Consider the FFT graph
F
(
k
)
on
m
=
2
k
inputs. Show that the subgraph connecting
inputs to any one output is a complete binary tree on
m
leaves.
10.12 Consider a directed acyclic graph with
n
vertices, some of which have out-degree greater
than 2. (a) Show that if each vertex of out-degree
k>
2 is replaced by a binary tree
with
k
leaves and edges directed from the root to the leaves, the number of vertices in
the graph is at most doubled. (b) Show that replacing vertices with in-degree greater
than 2 with binary trees also at most doubles the number of vertices in the graph.
EXTREME TRADEOFFS WITH PEBBLING
10.13 Let
N
(
k
)
be the number of vertices in the graph
H
k
discussed in Section
10.3
.Show
that the following recurrence holds for
N
(
k
)
:
N
(
k
)=
N
(
k
−
1
)+
4
k
+
3
Show that
N
(
k
)=
2
k
2
+
5
k
−
6for
k
≥
2since
N
(
2
)=
12.
10.14 Construct a new family
{
G
k
}
of graphs with fan-in 2 at each vertex from the graphs
{
by replacing the tree in Fig.
10.4
by a pyramid graph in
k
inputs and the bipartite
graph with the graph
E
k
showninFig.
10.23
. Show that each output of
E
k
can be
pebbled with
k
pebbles but that after pebbling any one output there is at least one path
without pebbles between the input and every other output. Show also that with
k
+
1
pebbles
E
k
can be pebbled without repebbling any vertex.
Let
T
k
(
S
)
be the number of steps to pebble
G
k
with
S
pebbles. Using the above facts,
show the following:
a)
N
(
k
)=
H
k
}
=
O
(
n
4
)
b)
S
min
(
G
k
)=
k
c)
T
k
(
k
+
1
)=
N
(
k
)
d)
T
k
(
k
)=
2
Ω(
N
(
k
)
1
/
4
log
N
(
k
))
|
G
k
|
Outputs
Inputs
u
2
u
k
u
k
+
1
u
1
k
Figure 10.23
The graph
E
k
used in the construction of the family
{G
k
}
.
Search WWH ::
Custom Search