Local Reconstructors and Tolerant Testers for Connectivity and Diameter

Local Reconstructors and Tolerant Testers for Connectivity and Diameter
复制标题

连接性和直径的本地重构器和容差测试器

DOI：
--
复制
发表时间：
2012
期刊：
International Workshop and International Workshop on Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
影响因子：
--
通讯作者：
R. Rubinfeld
R. Rubinfeld
中科院分区：
--
文献类型：
--
作者：
Andrea Campagna;Alan J. X. Guo;R. Rubinfeld

文献摘要

被引文献

相似文献

Graph属性的本地属性重建器是一种算法，它给定对具有“接近”属性的图形的邻接列表的访问，可提供对图形“校正”的邻接矩阵的访问，即。具有属性并接近此模型的属性，我们在无向图中实现了连接性和k-连接性的属性，并在有向图中的强属性。我们提出了一种将本地重建器（作为校正图的“邻接矩阵甲板”）转换为“邻接”列表的方法。获取局部重建者的k连接性。
A local property reconstructor for a graph property is an algorithm which, given oracle access to the adjacency list of a graph that is “close” to having the property, provides oracle access to the adjacency matrix of a “correction” of the graph, i.e. a graph which has the property and is close to the given graph. For this model, we achieve local property reconstructors for the properties of connectivity and k-connectivity in undirected graphs, and the property of strong connectivity in directed graphs. Along the way, we present a method of transforming a local reconstructor (which acts as a “adjacency matrix oracle” for the corrected graph) into an “adjacency list oracle”. This allows us to recursively use our local reconstructor for (k − 1)-connectivity to obtain a local reconstructor for k-connectivity.