Portal de Periódicos da CAPES

Local Reconstructors and Tolerant Testers for Connectivity and Diameter

2013; Springer Science+Business Media; Linguagem: Inglês

10.1007/978-3-642-40328-6_29

1611-3349

Andrea Campagna, Alan Guo, Ronitt Rubinfeld,

Stochastic Gradient Optimization Techniques

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.