膨胀图及其在随机算法中的应用
膨胀图是有很好连通性的稀疏图。一个膨胀图族是具有相同膨胀系数的一类正则膨胀图。本文从组合学角度对膨胀图及膨胀图族的概念、性质进行讨论。用概率方法证明了3-正則膨胀图族的存在性,井证明了2-正则膨胀图族的不存在性,提出了一类3-正則非膨胀图──塔形图的概念。按时间复杂度可将膨胀图分为弱可构造的和强可构造的。膨胀图的扩张图仍然是膨胀图,通过应用实例说明利用膨胀图能够降低随机算法对随机位的依赖程度。
膨胀图 正则图 塔形图 随机算法
吴占斌 徐德志
贵州大学计算机科学与技术学院 贵阳 550025
国内会议
西安
中文
327-331
2007-09-20（万方平台首次上网日期，不代表论文的发表时间）