Mean analysis of an online algorithm for the vertex cover problem

DOI10.1016/j.ipl.2008.12.021zbMath1215.68274MaRDI QIDQ987781

Christian Laforest, Etienne Birmelé, François Delbot

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 algorithm; on-line algorithm; graphs; vertex cover; mean analysis

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68W27: Online algorithms; streaming algorithms

Cites Work

• A better list heuristic for vertex cover
• On-line vertex-covering
• A list heuristic for vertex cover
• Unnamed Item
• Unnamed Item