Sublinear graph approximation algorithms
DOI10.1007/978-3-642-16367-8_9zbMATH Open1310.05202OpenAlexW1508435774MaRDI QIDQ4933367FDOQ4933367
Publication date: 12 October 2010
Published in: Property Testing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-16367-8_9
Recommendations
- An improved constant-time approximation algorithm for maximum~matchings
- A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
- Improved constant-time approximation algorithms for maximum matchings and other optimization problems
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Distance Approximation in Bounded-Degree and General Sparse Graphs
Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Cites Work
- Title not available (Why is that?)
- Approximation algorithms for combinatorial problems
- Graph minors. XX: Wagner's conjecture
- On the ratio of optimal integral and fractional covers
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Property testing in bounded degree graphs
- A Separator Theorem for Planar Graphs
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- On Constant Time Approximation of Parameters of Bounded Degree Graphs
- Title not available (Why is that?)
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- \(L^{2}\)-spectral invariants and convergent sequences of finite graphs
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- Local Graph Partitions for Approximation and Testing
- The price of being near-sighted
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
Cited In (8)
- Title not available (Why is that?)
- Algorithms on Subtree Filament Graphs
- Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs
- Sublinear randomized algorithms for skeleton decompositions
- Sublinear-time algorithms for approximating graph parameters
- Sublinear Random Access Generators for Preferential Attachment Graphs
- Title not available (Why is that?)
- Algorithms on subgraph overlap graphs
This page was built for publication: Sublinear graph approximation algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933367)
