Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs

DOI10.1016/j.disopt.2017.09.001zbMath1506.68067MaRDI QIDQ1662108

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

Publication date: 17 August 2018

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2017.09.001

zbMATH Keywords

graph algorithms; approximation algorithms; nonlinear program; combinatorial algorithms; maximum coverage

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

90C30: Nonlinear programming

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

90C27: Combinatorial optimization

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

68W25: Approximation algorithms