Testing the diameter of graphs
Testing the diameter of graphs
复制标题
测试图的直径
DOI：
10.1007/978-3-540-48413-4_9
复制
发表时间：
1999
影响因子：
1
通讯作者：
D. Ron
中科院分区：
文献类型：
--
作者：
Michal Parnas;D. Ron
我们提出了一个测试图属性的通用模型，该模型扩展并简化了Goldreich和罗恩的有界度模型[有界度图中的属性测试，第31届ACM计算理论研讨会论文，1997年，第31页]。406-415.]在这个模型中，我们提出了一系列算法，测试一个图的直径是否由给定的参数D限制，或者是否与任何直径不超过β（D）的图相距很远。函数β（D）的范围在D+4和4D+2之间，这取决于算法。我们所有的算法运行在时间多项式的1/2。© 2002威利期刊公司随机结构。 20：165-183，2002
We propose a general model for testing graph properties, which extends and simplifies the bounded degree model of Goldreich and Ron [Property Testing in Bounded Degree Graphs, Proc. 31st Annual ACM Symposium on the Theory of Computing, 1997, pp. 406–415.] In this model, we present a family of algorithms that test whether the diameter of a graph is bounded by a given parameter D, or is ϵ‐far from any graph with diameter at most β(D). The function β(D) ranges between D+4 and 4D+2, depending on the algorithm. All our algorithms run in time polynomial in 1/ϵ. © 2002 Wiley Periodicals, Inc. Random Struct. Alg. 20: 165–183, 2002