Computation of best possible low degree expanders |
| |
Authors: | Stefan Hougardy |
| |
Affiliation: | a Forschungsinstitut für Diskrete Mathematik, Universität Bonn, Lennéstr. 2, 53113 Bonn, Germany b Institut für Informatik, Humboldt-Universität zu Berlin, 10099 Berlin, Germany |
| |
Abstract: | We present an algorithm for computing a best possible bipartite cubic expander for a given number of vertices. Such graphs are needed in many applications and are also the basis for many results in theoretical computer science. Known construction methods for expander graphs yield expanders that have a fairly poor expansion compared to the best possible expansion. Our algorithm is based on a lemma which allows to calculate an upper bound for the expansion of cubic bipartite graphs. |
| |
Keywords: | Expander graph Orderly algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|