首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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=lfloorclognrfloor 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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号