Mean analysis of an online algorithm for the vertex cover problem

DOI10.1016/J.IPL.2008.12.021zbMath1215.68274OpenAlexW2088806939MaRDI QIDQ987781

Etienne Birmelé, Christian Laforest, 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 algorithmon-line algorithmgraphsvertex covermean analysis

Mathematics Subject Classification ID

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

Related Items (1)

Algorithm for online 3-path vertex cover

Cites Work

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

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