A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs

DOI10.1007/978-3-662-49529-2_18zbMath1475.68473arXiv1409.6952OpenAlexW1709760619MaRDI QIDQ2802943

Édouard Bonnet, Bruno Escoffier, Georgios Stamoulis, Vangelis Th. Paschos

Publication date: 3 May 2016

Published in: LATIN 2016: Theoretical Informatics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.6952

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (1)

Better streaming algorithms for the maximum coverage problem

This page was built for publication: A 0.821-Ratio Purely Combinatorial Algorithm for Maximum k-vertex Cover in Bipartite Graphs