Local graph partitions for approximation and testing

Local graph partitions for approximation and testing

We introduce a new tool for approximation and testing algorithms called partitioning oracles. We develop methods for constructing them for any class of bounded-degree graphs with an excluded minor, and in general, for any hyperfinite class of bounded-degree graphs. These oracles utilize only local c...

Full description

Bibliographic Details
Main Authors: Hassidim, Avinatan, Kelner, Jonathan Adam, Nguyen, Huy N., Onak, Krzysztof
Other Authors: Massachusetts Institute of Technology. Department of Materials Science and Engineering
Format: Article
Language:en_US
Published: Institute of Electrical and Electronics Engineers 2010
Subjects:
constant time algorithms
approximation algorithms
separator theorem
Online Access:http://hdl.handle.net/1721.1/59442
https://orcid.org/0000-0002-4257-4198

Internet

http://hdl.handle.net/1721.1/59442
https://orcid.org/0000-0002-4257-4198

Similar Items