On constant time approximation of parameters of bounded degree graphs

DOI10.1007/978-3-642-16367-8_14MaRDI QIDQ4933372zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

dominating setindependence numberconstant time approximation

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Randomized algorithms (68W20) Approximation algorithms (68W25) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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

Cites work

• scientific article; zbMATH DE number 1182757 (Why is no real title available?)
• scientific article; zbMATH DE number 1559556 (Why is no real title available?)
• scientific article; zbMATH DE number 1445320 (Why is no real title available?)
• scientific article; zbMATH DE number 3189017 (Why is no real title available?)
• Approximating the independence number via the -function
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Distance Approximation in Bounded-Degree and General Sparse Graphs
• High degree graphs contain large-star factors
• Inapproximability of vertex cover and independent set in bounded degree graphs
• Independence numbers of locally sparse graphs and a Ramsey type problem
• On Turan's theorem for sparse graphs
• On the independence number of 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)