Testing Expansion in Bounded-Degree Graphs
Testing Expansion in Bounded-Degree Graphs
复制标题
测试有界度图中的扩展
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
C. Sohler
中科院分区：
文献类型：
--
作者：
A. Czumaj;C. Sohler
我们考虑在有限度图中测试扩展的问题。我们专注于顶点扩展的概念：alpha-expander是图G =（v，e），其中最多| v |/2顶点的均匀subse u sube v的大小至少具有alphaldr |。 u |。我们的主要结果是，可以将良好的扩展器与远离时间上弱扩展器（RadICN）的图形区分开。我们证明，Goldreich和Ron（2000）提出的属性测试算法具有适当的集合参数，以至少2/3的概率接受每个alpha-expander，并拒绝每个epsiv far a alpha* - expand of Alpha* - expander的图表至少具有概率。 2/3，其中alpha*= theta（alpha2/（d2log（n/epsiv））），d是最大程度图。该算法假定具有邻接列表图表的有界数学图模型，其运行时间为O（d2（radicn log（n/epsiv））/alpha2epsiv3）。
We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an alpha-expander is a graph G = (V, E) in which even-subset U sube V of at most |V|/2 vertices has a neighborhood of size at least alphaldr|U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time O tilde(radicn). We prove that the property testing algorithm proposed by Goldreich and Ron (2000) with appropriately set parameters accepts every alpha-expander with probability at least 2/3 and rejects every graph that is epsiv-far from an alpha*-expander with probability at least 2/3, where alpha*=Theta(alpha2/(d2log (n/epsiv))) and d is the maximum degree of the graphs. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is O(d2(radicn log (n/epsiv))/alpha2epsiv3).