Local Algorithms for Sparse Spanning Graphs

Local Algorithms for Sparse Spanning Graphs

Show other versions (1)

We initiate the study of the problem of designing sublinear-time (local) algorithms that, given an edge (u,v) in a connected graph G = (V,E), decide whether (u,v) belongs to a sparse spanning graph G' = (V,E') of G. Namely, G' should be connected and |E'| should be upper bounded...

Full description

Bibliographic Details
Main Authors: Levi, Reut, Ron, Dana, Rubinfeld, Ronitt
Other Authors: Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory
Format: Article
Language:en_US
Published: Schloss Dagstuhl 2016
Online Access:http://hdl.handle.net/1721.1/101032
https://orcid.org/0000-0002-4353-7639

Internet

http://hdl.handle.net/1721.1/101032
https://orcid.org/0000-0002-4353-7639

Similar Items