Superconcentrators of density 25.3.

MaRDI QIDQ4558662zbMATH OpenFDO

Authors Vladimir Kolmogorov, Michal Rolínek

Publication date 29 November 2018

Full work available at URL https://arxiv.org/abs/1405.7828

zbMATH Keywords

densitydigraphnode-disjoint pathssuperconcentrator

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Density (toughness, etc.) (05C42)

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. We prove the existence of such superconcentrators with asymptotic density $25.3$ (where the density is the number of edges divided by $N$). The previously best known densities were $28$ cite{Scho2006} and $27.4136$ cite{YuanK12}.

Recommendations

• Smaller superconcentrators of density 28
• Smaller Explicit Superconcentrators
• scientific article; zbMATH DE number 3974994
• scientific article; zbMATH DE number 3864514
• Superconcentrators of depths 2 and 3; odd levels help (rarely)

Cited in

(8)

• Superconcentrators of depths 2 and 3; odd levels help (rarely)
• Self-routing superconcentrators
• scientific article; zbMATH DE number 3864514 (Why is no real title available?)
• scientific article; zbMATH DE number 3974994 (Why is no real title available?)
• scientific article; zbMATH DE number 1535255 (Why is no real title available?)
• Tradeoffs in Depth-Two Superconcentrators
• A geometric construction of a superconcentrator of depth 2
• Smaller superconcentrators of density 28

This page was built for publication: Superconcentrators of density 25.3.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4558662)