Information Technology Reference
In-Depth Information
n
to pebble it, whereas for
S
c
2
(
d
)
S
J
(
n
)
all graphs on
n
vertices can be pebbled with a
polynomial number of steps? They show that there is such a
jump value for space
and that
S
J
(
n
)=Θ(
n/
log log
n
)
.Sinceallgraphson
n
vertices can be pebbled with
O
(
n/
log
n
)
space, their result shows there exist graphs on
n
vertices that require time exponential in
n
when pebbled with this number of pebbles.
≥
10.7 Upper Bounds on Space*
We establish upper bounds on space for the class
(
n
,
d
)
of directed acyclic graphs on
n
vertices that have maximum in-degree
d
and out-degree 2. We limit the out-degree to 2
because many straight-line programs with fan-out
k>
2 (and their associated DAGs) can
be reorganized so that each computation with fan-out
k
can be replaced by a binary tree of
replicating subcomputations in which edges are directed from the root to the leaves. This at
most doubles the number of vertices in the graph. (See Problem
10.12
.)
G
THEOREM
10.7.1
Let
G
(
n
,
d
)
be graphs with
n
vertices, in-degree
d
,andout-degree
2
for
d
fixed. Then
S
min
(
n
,
d
)
, the minimum space needed to pebble any DAG in
G
(
n
,
d
)
,satisfies
S
min
(
n
,
d
)=
O
(
n/
log
n
)
.
Proof
Let
E
min
(
p
,
d
)
be the minimum number of edges in any graph in
G
(
n
,
d
)
that re-
quires
p
pebbles in the pebble game. We show that
E
min
(
p
,
d
)
≥
cp
log
2
p
for some
constant
c>
0. From this it follows that
p
≤
2
(
E
min
(
p
,
d
)
/c
)
/
log
2
(
E
min
(
p
,
d
)
/c
)
when
p
2
c
. (See Problem
10.3
.)
Consider a graph
G
=(
V
,
E
)
in
≥
2and
E
min
(
p
,
d
)
≥
G
(
n
,
d
)
with
|
E
|
edges. The number of edges incident
|
=(
d
+
2
)
n
. The upper bound on the number of pebbles,
p
, follows from this fact and the
previous discussion.
Let
G
=(
V
,
E
)
in
|
E
|
. Since each vertex has at most
d
+
2 incident edges, 2
|
E
|≤
(
d
+
2
)
|
V
on vertices is 2
G
(
n
,
d
)
require
p
pebbles. An edge in
E
is a pair of vertices
(
u
,
v
)
.
Let
V
1
⊆
V
1
.
Thus, every vertex in
V
2
requires more than
p/
2 pebbles. Let
E
i
,
i
=
1, 2, be the set of
edges both of whose endpoints are in
V
i
.Let
G
i
=(
V
i
,
E
i
)
.Let
A
=
E
V
be vertices that can be pebbled with
p/
2 or fewer pebbles. Let
V
2
=
V
−
−
(
E
1
∪
E
2
)
;that
is,
A
is the set of edges joining vertices in
V
1
and
V
2
.
We now show that there exists a vertex in
G
2
that requires more than
p/
2
d
pebbles
if the pebble game is played on
G
2
only. Suppose not. Then we show that every vertex in
G
can be pebbled with fewer than
p
pebbles. Certainly every vertex in
V
1
can be pebbled with
fewer than
p
pebbles. Consider vertices in
V
2
. We show they can be pebbled with fewer than
p
pebbles, thereby establishing a contradiction.
Let
ν
−
d
or fewer pebbles when
G
2
alone is pebbled. In
pebbling
ν
as part of the complete graph
G
, we may need to pebble a vertex
ω
∈
V
2
be pebbled with
p/
2
−
V
2
some of
whose immediate predecessors are in
V
1
. As we encounter such vertices
ω
, advance a pebble
to each of
ω
's predecessors in
V
1
one at at time until all predecessors of
ω
are pebbled. After
pebbling a predecessor in
V
1
, remove pebbles in
V
1
not on such predecessors. When all
of
ω
's predecessors in
V
1
have been pebbled, pebble
ω
itself using one of the
p/
2
∈
−
d
or
fewer pebbles reserved for pebbling on
V
2
.Thisstrategyusesatmost
p/
2
+
d
−
1 pebbles
on vertices in
V
1
,atmost
d
−
1 for all but the last predecessor in
V
1
and at most
p/
2
Search WWH ::
Custom Search