Name
Abstract | ||
|---|---|---|
An N-superconcentrator is a directed, acyclic graph with N input nodes and N output nodes such that every subset of the inputs and every subset of the outputs of same cardinality can be connected by node-disjoint paths. It is known that linear-size and bounded-degree superconcentrators exist. Here it is proved that such superconcentrators exist (by a random construction of certain expander graphs as building blocks) having density 28 (where the density is the number of edges divided by N). The best known density before this paper was 34.2 [U. Schöning, Construction of expanders and superconcentrators using Kolmogorov complexity, J. Random Structures Algorithms 17 (2000) 64-77] or 33 [L.A. Bassalygo, Personal communication, 2004]. |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1016/j.ipl.2006.01.006 | Inf. Process. Lett. |
Keywords | Field | DocType |
l.a. bassalygo,u. schoning,bounded-degree superconcentrators,smaller superconcentrators,kolmogorov complexity,combinatorial problem,random construction,superconcentrator,n output,n input node,acyclic graph,u. sch,j. random structures algorithms,known density,computational complexity,directed acyclic graph,expander graph | Discrete mathematics,Combinatorics,Random graph,Expander graph,Division (mathematics),Kolmogorov complexity,Cardinality,Directed graph,Directed acyclic graph,Mathematics,Computational complexity theory | Journal |
Volume | Issue | ISSN |
98 | 4 | 0020-0190 |
Citations | PageRank | References |
1 | 0.36 | 7 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Uwe Schöning | 1 | 998 | 105.69 |