Information Technology Reference
In-Depth Information
The graph
H
(
k
)
has
n
(
k
)=
|
H
(
k
)
|
vertices, where
n
(
k
)
satisfies the following:
n
(
8
)=
c
2
8
n
(
k
+
1
)=
2
n
(
k
)+(
2
c
+
4
)
2
k
7
)
c
2
k
+(
k
8
)
2
k
+
1
,ascanbeshowndirectly.
The solution to the recurrence is
n
(
k
)=(
k
−
−
The graph
H
(
k
)
is in
(
n
(
k
)
,2
)
.
Important subgraphs of
H
(
k
+
1
)
have the superconcentrator property, as we now show.
This result is applied in the subsequent lemma to derive bounds on the amount of space used
to pebble outputs of
H
(
k
+
1
)
.
G
LEMMA
10.8.2
The subgraphs of
H
(
k
+
1
)
on
2
k
inputs and
2
k
outputs defined by vertices and
edges on paths from either inputs in
I
t
or inputs in
I
b
to the outputs of
SC
1
and
H
1
(
k
)
have the
2
k
-superconcentrator property.
Proof
The superconcentrator property applies to the outputs of
SC
1
(
k
)
by definition. Note
that the
j
th input of
H
1
(
k
)
is connected to its
j
th output by an individual edge for 1
≤
2
k
.Thus,any
r
outputs of
H
1
(
k
)
have vertex-disjoint paths to the corresponding inputs of
H
1
(
k
)
. By the superconcentrator property of
SC
1
(
k
)
, there are vertex-disjoint paths from
these outputs of
SC
1
(
k
)
to any
r
of its inputs. These statements obviously apply to inputs
in
I
t
and
I
b
.
≤
j
Our goal is to show that pebbling the graph
H
(
k
)
requires a number of pebbles propor-
tional to
n
(
k
)
/
log
n
(
k
)
. To do this we establish the following stronger condition, which
implies the desired result.
LEMMA
10.8.3
Let
c
1
=
14
/
256
,
c
2
=
3
/
256
,
c
3
=
34
/
256
,and
c
4
=
1
/
256
. To pebble at
least
c
1
2
k
outputs of
H
(
k
)
in any order from an initial placement of at most
c
2
2
k
pebbles requires
there be a time interval
[
t
1
,
t
2
]
during which at least
c
3
2
k
inputs are pebbled and at least
c
4
2
k
pebbles remain on the graph.
Proof
The proof is by induction on
k
with
k
=
8 as the base case. For the base case,
consider pebbling
c
1
2
k
=
14 outputs during a time interval
[
0,
t
]
from an initial placement
of no more than
c
2
2
k
=
3 pebbles.
By Problem
10.27
any four outputs of
SC
(
8
)
are connected via pebble-free paths to
−
3
=
253 inputs. At least one of these four outputs, say
v
, has pebble-free paths to 64
256
253
/
4
inputs. Let
t
1
−
=
1 be the last time at which all 64 of these inputs have pebble-free
paths to
v
.Let
t
2
be the last time at which a pebble is placed on these 64 inputs. During the
time interval
[
t
1
,
t
2
]
at least 64
c
3
2
k
inputs are pebbled and at least one pebble remains
on the graph; that is, at least
c
4
2
k
pebbles remain. This establishes the base case.
Now assume the conditions of the lemma (our inductive hypothesis) hold for
k
.We
show they hold for
k
+
1. Assume that at least
c
1
2
k
+
1
outputs of
H
(
k
+
1
)
are pebbled in
any order from an initial placement of at most
c
2
2
k
+
1
pebbles during a time interval
[
t
a
,
t
b
]
.
We consider four cases including the following two cases. There is an interval
[
t
1
,
t
2
]
≥
⊆
[
t
a
,
t
b
]
during which at least
c
2
2
k
pebbles are always on the graph and at least
c
3
2
k
outputs
of either (1)
SC
1
(
k
)
,or(2)
H
1
(
k
)
are pebbled. By Lemma
10.8.2
the subgraph of
H
(
k
+
1
)
consisting of paths from
I
t
(and
I
b
) to the outputs of each of these graphs constitutes a 2
k
-
superconcentrator. This is the only fact about these two cases that we use. Without loss of
generality, we show the hypothesis holds for the first of them.
Search WWH ::
Custom Search