Mean analysis of an online algorithm for the vertex cover problem
type: Item
instance of: scholarly article
title: Mean analysis of an online algorithm for the vertex cover problem
zbMATH Open document ID: 1215.68274
author: Etienne Birmelé
author: François Delbot
author: Christian Laforest
published in: Information Processing Letters
publication date: 2010-08-16T00:00:00Z
Mathematics Subject Classification ID: 68W27
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5771235
zbMATH Keywords: graphs
zbMATH Keywords: vertex cover
zbMATH Keywords: approximation algorithm
zbMATH Keywords: mean analysis
zbMATH Keywords: on-line algorithm
MaRDI profile type: Publication
full work available at URL: j.ipl.2008.12.021
OpenAlex ID: W2088806939
cites work: Q4258216
cites work: A list heuristic for vertex cover
cites work: A better list heuristic for vertex cover
cites work: On-line vertex-covering
cites work: Q4198056
DOI: 10.1016/J.IPL.2008.12.021
Recommended article: On-line vertex-covering
Recommended article: Q4414489
Recommended article: Improved analysis of the online set cover problem with advice
Recommended article: On-line and off-line approximation algorithms for vector covering problems
Recommended article: Online algorithms for the maximum \(k\)-interval coverage problem
Recommended article: Experimental analysis of approximation algorithms for the vertex cover and set covering problems
Recommended article: A new measure for the study of on-line algorithms
Recommended article: On the Approximability of the Vertex Cover and Related Problems
Recommended article: Convergence analysis of online algorithms
description: scientific article; zbMATH DE number 5771235