On Constant Time Approximation of Parameters of Bounded Degree Graphs

DOI10.1007/978-3-642-16367-8_14zbMath1309.68213OpenAlexW1527654424MaRDI QIDQ4933372

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

independence numberdominating setconstant time approximation

Mathematics Subject Classification ID

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

Related Items (2)

Sublinear Graph Approximation Algorithms ⋮ Simple and local independent set approximation

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• On Turan's theorem for sparse graphs
• Approximating the independence number via the \(\vartheta\)-function
• High degree graphs contain large-star factors
• Distance Approximation in Bounded-Degree and General Sparse Graphs
• Approximations of Weighted Independent Set and Hereditary Subset Problems
• Independence numbers of locally sparse graphs and a Ramsey type problem
• On the independence number of sparse graphs

This page was built for publication: On Constant Time Approximation of Parameters of Bounded Degree Graphs