Local Reconstructors and Tolerant Testers for Connectivity and Diameter
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 t...
| Hlavní autoři: | , , |
|---|---|
| Další autoři: | |
| Médium: | Článek |
| Jazyk: | en_US |
| Vydáno: |
Springer-Verlag
2014
|
| On-line přístup: | http://hdl.handle.net/1721.1/90839 |