Testing properties of graphs and functions
Testing properties of graphs and functions
复制标题
测试图形和函数的属性
DOI：
10.1007/s11856-010-0060-7
复制
发表时间：
2008
影响因子：
1
通讯作者：
Balázs Szegedy
中科院分区：
文献类型：
--
作者：
L. Lovász;Balázs Szegedy
我们定义了图性测试问题的一个解析形式，它可以表示为研究一个未知的二变量对称函数，通过从它的定义域中抽样，并研究以函数值作为边概率时所得到的随机图。我们给出了这种方法可测试性质的刻画，并将有关“大图”的一些结果推广到这种情况，这些结果可以应用于最初的图论性质测试。特别地，我们给出了可测图性质的一个新的组合刻画。此外，我们定义了一类包含所有遗传性质的图性质(柔性性质)，并将Alon、Shapira、Fischer、Newman和Stav的各种结果从遗传性质推广到柔性性质。
We define an analytic version of the graph property testing problem, which can be formulated as studying an unknown 2-variable symmetric function through sampling from its domain and studying the random graph obtained when using the function values as edge probabilities. We give a characterization of properties testable this way, and extend a number of results about “large graphs” to this setting.These results can be applied to the original graph-theoretic property testing. In particular, we give a new combinatorial characterization of the testable graph properties. Furthermore, we define a class of graph properties (flexible properties) which contains all the hereditary properties, and generalize various results of Alon, Shapira, Fischer, Newman and Stav from hereditary to flexible properties.