On constant time approximation of parameters of bounded degree graphs
DOI10.1007/978-3-642-16367-8_14zbMATH Open1309.68213OpenAlexW1527654424MaRDI QIDQ4933372FDOQ4933372
Authors: Noga Alon 
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_14
Recommendations
- scientific article; zbMATH DE number 1003268
- Improved approximations of independent sets in bounded-degree graphs
- Improved constant-time approximation algorithms for maximum matchings and other optimization problems
- An improved constant-time approximation algorithm for maximum~matchings
- On approximation properties of the independent set problem for low degree graphs
Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Cites Work
- On the independence number of sparse graphs
- Approximations of Weighted Independent Set and Hereditary Subset Problems
- Inapproximability of vertex cover and independent set in bounded degree graphs
- Approximating the independence number via the \(\vartheta\)-function
- Independence numbers of locally sparse graphs and a Ramsey type problem
- Title not available (Why is that?)
- High degree graphs contain large-star factors
- On Turan's theorem for sparse graphs
- Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Distance Approximation in Bounded-Degree and General Sparse Graphs
Cited In (8)
- An improved constant-time approximation algorithm for maximum~matchings
- Improved constant-time approximation algorithms for maximum matchings and other optimization problems
- Simple and local independent set approximation
- Borel oracles. An analytical approach to constant-time algorithms
- A tight upper bound on acquaintance time of graphs
- Sublinear graph approximation algorithms
- Constant-factor approximation of the domination number in sparse graphs
- Approximation algorithms in graphs with known broadcast time of the base graph
This page was built for publication: On constant time approximation of parameters of bounded degree graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4933372)
