Advertisement
Published in:
2006 | OriginalPaper | Chapter
Tradeoffs in Depth-Two Superconcentrators
Authors : Chinmoy Dutta, Jaikumar Radhakrishnan
Published in: STACS 2006
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
An
N
-
superconcentrator
is a directed graph with
N
input vertices and
N
output vertices and some intermediate vertices, such that for
k
=1, 2, ...,
N
, between any set of
k
input vertices and any set of
k
output vertices, there are
k
vertex disjoint paths. In a
depth-twoN
-superconcentrator each edge either connects an input vertex to an intermediate vertex or an intermediate vertex to an output vertex. We consider tradeoffs between the number of edges incident on the input vertices and the number of edges incident on the output vertices in a depth-two
N
-superconcentrator. For an
N
-superconcentrator
G
, let
a
(
G
) be the average degree of the input vertices and
b
(
G
) be the average degree of the output vertices. Assume that
b
(
G
) ≥
a
(
G
). We show that there is a constant
k
1
> 0 such that
$a(G)log (\frac{2b(G)}{a(G)}) log b(G) \geq k_1 \cdot log^2 N$
.