Testing properties of graphs and functions |
| |
Authors: | László Lovász Balázs Szegedy |
| |
Affiliation: | 1.Institute of Mathematics,E?tv?s Loránd University,Budapest,Hungary;2.Toronto,Canada |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|