On Constant Time Approximation of Parameters of Bounded Degree Graphs
type: Item
instance of: scholarly article
title: On Constant Time Approximation of Parameters of Bounded Degree Graphs
zbMATH Open document ID: 1309.68213
DOI: 10.1007/978-3-642-16367-8_14
author: Noga Alon
published in: Property Testing
publication date: 2010-10-12T00:00:00Z
Mathematics Subject Classification ID: 68W20
Mathematics Subject Classification ID: 05C69
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68W25
zbMATH DE Number: 5799061
zbMATH Keywords: independence number
zbMATH Keywords: dominating set
zbMATH Keywords: constant time approximation
MaRDI profile type: MaRDI publication profile
full work available at URL: 978-3-642-16367-8 14
OpenAlex ID: W1527654424
cites work: On Turan's theorem for sparse graphs
cites work: Independence numbers of locally sparse graphs and a Ramsey type problem
cites work: Approximating the independence number via the \(\vartheta\)-function
cites work: High degree graphs contain large-star factors
cites work: Q3002828
cites work: Q5725269
cites work: Q4527008
cites work: Q4400840
cites work: Approximations of Weighted Independent Set and Hereditary Subset Problems
cites work: Q4952635
cites work: Distance Approximation in Bounded-Degree and General Sparse Graphs
cites work: Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
cites work: On the independence number of sparse graphs
description: scientific article; zbMATH DE number 5799061