Recursive construction for 3-regular expanders
作者： M. Ajtai
DOI: 10.1007/BF01302963
关键词: Expander graph 、 Mathematics 、 Graph (abstract data type) 、 Combinatorics
摘要: We present an algorithm which inn 3 (logn)3 time constructs a 3-regular expander graph onn vertices. In each step we substitute pair of edges the by new so that total number cycles lengths=⌊clogn⌋ decreases (for some fixed absolute constantc). When reach local minimum in lengths is expander.
springer.com
sci-hub.se 参考文章(10)
Miklós Ajtai, János Komlós, William L. Steiger, Endre Szemerédi, Almost Sorting in one Round. Adv. Comput. Res.. ,vol. 5, pp. 117- 125 ,(1989)
M. Ajtai, J. Komlós, E. Szemerédi, Sorting inc logn parallel steps Combinatorica. ,vol. 3, pp. 1- 19 ,(1983) , 10.1007/BF02579338
Nicholas Pippenger, Sorting and selecting in rounds SIAM Journal on Computing. ,vol. 16, pp. 1032- 1038 ,(1987) , 10.1137/0216066
A Lubotzky, R Phillips, P Sarnak, Explicit expanders and the Ramanujan conjectures symposium on the theory of computing. pp. 240- 246 ,(1986) , 10.1145/12130.12154
N Alon, V.D Milman, λ1, Isoperimetric inequalities for graphs, and superconcentrators Journal of Combinatorial Theory, Series B. ,vol. 38, pp. 73- 88 ,(1985) , 10.1016/0095-8956(85)90092-9
Leslie G. Valiant, Graph-theoretic properties in computational complexity Journal of Computer and System Sciences. ,vol. 13, pp. 278- 285 ,(1976) , 10.1016/S0022-0000(76)80041-4
Ofer Gabber, Zvi Galil, Explicit constructions of linear-sized superconcentrators Journal of Computer and System Sciences. ,vol. 22, pp. 407- 420 ,(1981) , 10.1016/0022-0000(81)90040-4
Harold Abelson, A note on time-space tradeoffs for computing continuous functions Information Processing Letters. ,vol. 8, pp. 215- 217 ,(1979) , 10.1016/0020-0190(79)90027-9
Miklós Ajtai, János Komlós, W.L. Steiger, Endre Szemerédi, Optimal parallel selection had complexity O (log log N ) symposium on the theory of computing. ,vol. 38, pp. 125- 133 ,(1989) , 10.1016/0022-0000(89)90035-4
Miklós Ajtai, János Komlós, Endre Szemerédi, Deterministic simulation in LOGSPACE symposium on the theory of computing. pp. 132- 140 ,(1987) , 10.1145/28395.28410