Name
Abstract | ||
|---|---|---|
We show the existence of various versions of expander graphs using Kolmogorov complexity. This method seems superior to the usual "probabilistic construction". Also, the best known bounds on the size of expanders and superconcentrators can be obtained this way. In the case of (acyclic) superconcentrators we obtain the density 34. Also, we review related graph properties, like magnification, edge-magnification, isolation, and develop bounds based on the Kolmogorov approach. |
Year | Venue | Keywords |
|---|---|---|
1997 | SIROCCO | expander graph |
Field | DocType | Citations |
Discrete mathematics,Kolmogorov complexity,Mathematics | Conference | 3 |
PageRank | References | Authors |
0.55 | 17 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Uwe Schöning | 1 | 998 | 105.69 |
| Oberer Eselsberg | 2 | 3 | 0.88 |