Testing st -Connectivity
Testing st -Connectivity
复制标题
测试连接性
DOI：
10.1007/978-3-540-74208-1_28
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
I. Newman
中科院分区：
文献类型：
--
作者：
Sourav Chakraborty;E. Fischer;Oded Lachish;A. Matsliah;I. Newman
我们继续研究[9]中开始的定向模型中图的性质测试。在[9]中留下的一个主要问题是st-连通性的属性是否可以用恒定数量的查询来测试。在这里，我们对这个问题的回答是肯定的。为此，我们构造了一个非平凡的约化的st-连通性问题的问题，测试语言，可决定的分支程序，这是解决了在[11]。减少组合参数与浓度型引理证明了这一目的。与许多其他属性测试结果不同，这里得到的测试算法本身是非常重要的，而不仅仅是它的分析。
We continue the study, started in [9], of property testing of graphs in the orientation model. A major question which was left open in [9] is whether the property ofst-connectivity can be tested with a constant number of queries. Here we answer this question on the affirmative. To this end we construct a non-trivial reduction of thest-connectivity problem to the problem of testing languages that are decidable by branching programs, which was solved in [11]. The reduction combines combinatorial arguments with a concentration type lemma that is proven for this purpose. Unlike many other property testing results, here the resulting testing algorithm is highly non-trivial itself, and not only its analysis.