Sublinear Graph Approximation Algorithms
From MaRDI portal
Publication:4933367
DOI10.1007/978-3-642-16367-8_9zbMath1310.05202OpenAlexW1508435774MaRDI QIDQ4933367
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
Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Graph minors. XX: Wagner's conjecture
- \(L^{2}\)-spectral invariants and convergent sequences of finite graphs
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Approximation algorithms for combinatorial problems
- On the ratio of optimal integral and fractional covers
- A Characterization of the (Natural) Graph Properties Testable with One-Sided Error
- The price of being near-sighted
- Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs
- A Simple Parallel Algorithm for the Maximal Independent Set Problem
- A Separator Theorem for Planar Graphs
- On Constant Time Approximation of Parameters of Bounded Degree Graphs
- Approximating the distance to properties in bounded-degree and general sparse graphs
- Local Graph Partitions for Approximation and Testing
- An improved constant-time approximation algorithm for maximum~matchings
- Approximating the Minimum Spanning Tree Weight in Sublinear Time
- An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
- Property testing in bounded degree graphs
This page was built for publication: Sublinear Graph Approximation Algorithms
