Mean analysis of an online algorithm for the vertex cover problem

DOI10.1016/J.IPL.2008.12.021MaRDI QIDQ987781zbMATH OpenOpenAlexFDO

Authors Etienne Birmelé, François Delbot, Christian Laforest

Publication date 16 August 2010

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2008.12.021

zbMATH Keywords

approximation algorithmgraphsmean analysison-line algorithmvertex cover

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Recommendations

• On-line vertex-covering
• scientific article; zbMATH DE number 1953086
• Improved analysis of the online set cover problem with advice
• On-line and off-line approximation algorithms for vector covering problems
• On-line and off-line approximation algorithms for vector covering problems
• Online algorithms for the maximum \(k\)-interval coverage problem
• Experimental analysis of approximation algorithms for the vertex cover and set covering problems
• A new measure for the study of on-line algorithms
• On the approximability of the vertex cover and related problems
• Convergence analysis of online algorithms

Cites work

• A better list heuristic for vertex cover
• A list heuristic for vertex cover
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1330033 (Why is no real title available?)
• On-line vertex-covering

Cited in

(4)

• On-line vertex-covering
• Algorithm for online 3-path vertex cover
• Analytical and experimental comparison of six algorithms for the vertex cover problem
• Closing the Gap Between Theory and Practice: New Measures for On-Line Algorithm Analysis

This page was built for publication: Mean analysis of an online algorithm for the vertex cover problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q987781)