Information Technology Reference
In-Depth Information
n
,thereare
r
vertex-disjoint paths in
G
connecting these inputs and outputs. (Paths are
vertex-disjoint
if they have no vertices in common.)
≤
r
≤
1
For
n
=
2
k
Va l i an t [
343
]hasshowntheexistenceof
n
-superconcentrators
SC
(
k
)
that
have 2
k
inputs, 2
k
outputs, and
c
2
k
edges. Since his graphs have in-degree greater than 2,
replace vertices with in-degree
d>
2 with binary trees of
d
leaves, thereby at most doubling
the size of the graph. (See Problem
10.12
.) This provides the following result.
LEMMA
10.8.1
For some constant
c>
0
and each integer
k
and
n
=
2
k
there exists an
n
-
superconcentrator
SC
(
k
)
with
c
2
k
vertices.
8weconstruct
H
(
k
+
1
)
recursively from two copies
of
H
(
k
)
,twocopiesof
SC
(
k
)
, and extra edges, as suggested in Fig.
10.10
. Here edges are
directed from left to right. The 2
k
output vertices of the first (leftmost) copy of
SC
(
k
)
(called
SC
1
(
k
)
) are identified with the 2
k
input vertices of the first copy of
H
(
k
)
(called
H
1
(
k
)
),
the 2
k
output vertices of
H
1
(
k
)
are identified with the 2
k
input vertices of the second copy
of
H
(
k
)
(called
H
2
(
k
)
), and the 2
k
output vertices of
H
2
(
k
)
are identified with the 2
k
input
vertices of the second copy of
SC
(
k
)
(called
SC
2
(
k
)
). In addition, we introduce 2
k
+
1
new
input vertices and 2
k
+
1
new output vertices. The first (topmost) half of the new inputs (called
I
t
) are connected via individual edges to the inputs of
SC
1
(
k
)
. The second (bottommost) half
of the new inputs (called
I
b
) are also connected via individual edges to the inputs of
SC
1
(
k
)
.
The new inputs are connected individually to the new outputs. Finally, each output of
SC
2
(
k
)
is connected via individual edges to two new output vertices, one each in the top (called
O
t
)
and bottom half (called
O
b
)ofthenewoutputs.
We l e t
H
(
8
)=
SC
(
8
)
.For
k
≥
Inputs
Outputs
I
t
SC
1
(
k
)
H
1
(
k
)
H
2
(
k
)
SC
2
(
k
)
O
t
O
b
I
b
Figure 10.10
Agraph
H
(
k
+
1
)
requiring large minimum space.
Search WWH ::
Custom Search