Recursive construction for 3-regular expanders |
| |
Authors: | M Ajtai |
| |
Institution: | (1) IBM Almaden Research Center, San Jose, USA |
| |
Abstract: | We present an algorithm which inn
3 (logn)3 time constructs a 3-regular expander graph onn vertices. In each step we substitute a pair of edges of the graph by a new pair of edges so that the total number of cycles of lengths=clogn decreases (for some fixed absolute constantc). When we reach a local minimum in the number of cycles of lengths the graph is an expander. |
| |
Keywords: | 05 C 38 05 C 85 |
本文献已被 SpringerLink 等数据库收录! |