Information Technology Reference
In-Depth Information
for the last such predecessor, and at most
p/
2
−
d
pebbles on vertices in
V
2
, for a total of
at most
p
−
1. This is a contradiction. It follows that
G
2
requires at least
p/
2
−
d
+
1
pebbles when pebbled alone and must have at least
E
min
(
p/
2
−
d
+
1,
d
)
edges. Note that
E
min
(
p/
2
d
,
d
)
.
There is also some vertex in
G
1
that requires at least
p/
2
−
d
+
1,
d
)
≥
E
min
(
p/
2
−
d
vertices, as we show. By
assumption every vertex in
V
1
must be pebbled. Suppose that each can be pebbled with
p/
2
−
1 pebbles. There must be a vertex
η
in
V
2
all of whose predecessors are in
V
1
. (If not, we can always move backward from a vertex in
V
2
to one of its immediate
predecessors in
V
2
, a process that must terminate since the finite acyclic graph does not have
a cycle.) Thus, the vertex
η
can be pebbled with
p/
2
−
d
−
−
1 pebbles using the pebbling strategy
described in the preceding paragraph for
ω
, contradicting the definition of
V
2
. It follows
that
G
1
must have at least
E
min
(
p/
2
d
,
d
)
edges.
Consider now the set of edges
A
connecting vertices in
V
1
and
V
2
. f
−
|
A
|≥
p/
4,
E
min
(
p
,
d
)
≥
2
E
min
(
p/
2
−
d
,
d
)+
|
A
|
because both
G
1
and
G
2
have
E
min
(
p/
2
−
d
,
d
)
edges. If
<p/
4, pebbles can be placed on the endpoints of edges of
A
in
V
1
using at
most
p/
2
+
p/
4
|
A
|
3
p/
4 pebbles, with the strategy for
ω
given above. If we leave at
most
p/
4 pebbles on these vertices, 3
p/
4 pebbles are available to pebble the vertices in
V
2
.
If
V
2
does not require at least 3
p/
4 pebbles, we have a contradiction to the assumption that
p
pebbles are needed. Thus, there must be an output vertex
μ
that requires at least 3
p/
4
pebbles, for if not, none of its predecessors can require more.
We show that a graph requiring at least 3
p/
4 pebbles has a subgraph with at least
p/
(
4
d
)
fewer edges that requires at least
p/
2 pebbles. To see this, observe that some predecessor of
the output vertex
μ
requires at least 3
p/
4
−
1
≤
d
pebbles. Delete
μ
and all its incoming edges
to produce a subgraph with at least one fewer edge requiring at least 3
p/
4
−
d
pebbles.
Repeat this process
p/
(
4
d
)
times to produce the desired result. It follows that
G
2
has at least
E
min
(
p/
2,
d
)+
p/
(
4
d
)
edges.
Thus, when either
−
|
A
|≥
p/
4or
|
A
|
<p/
4, at least 2
E
min
(
p/
2
−
d
,
d
)+
p/
(
4
d
)
edges
are required, and
d
,
d
)+
p
4
d
E
min
(
p
,
d
)
≥
2
E
min
(
p/
2
−
The solution to this recurrence is
E
min
(
p
,
d
)
≥
cp
log
p
for some constant
c
≥
1
/
8
d
and a
sufficiently large value of
p
.
10.8
Lower Bound on Space for General Graphs*
Now that we have established that every graph in
(
n
,
d
)
can be pebbled with
O
(
n/
log
n
)
pebbles, we show that for all
n
there exists a graph
G
(
n
)
in
G
G
(
n
,
d
)
whose minimum space
requirement is at least
c
5
n/
log
n
for some constant
c
5
>
0.
The graph
G
(
n
)
is obtained from a recursively constructed graph
H
(
k
)
on 2
k
inputs and
2
k
outputs,
n/
2
<
2
k
2
k
vertices and no edges. The graph
H
(
k
)
is
≤
n
, by adding
n
−
composed of two copies of
H
(
k
−
1
)
and two copies of an
n
-superconcentrator, which is
defined below.
DEFINITION
10.8.1
An
n
-superconcentrator
is a directed acyclic graph
G
=(
V
,
E
)
with
n
input vertices and
n
output vertices and the property that for any
r
inputs and any
r
outputs,
Search WWH ::
Custom Search