2015/02/27 by Vangélis Th. Paschos, Paschos, Vangelis Th.
Computer Science · #Complexity and Algorithms in Graphs #Advanced Graph Theory Research #Computational Geometry and Mesh Generation
paper · pdf · doi:10.48550/arxiv.1502.07930
We propose a purely combinatorial algorithm for \mkvc in bipartite graphs, achieving approximation ratio~0.7. The only combinatorial algorithms currently known until now for this problem are the natural greedy algorithm, that achieves ratio 0.632, and an easy~2/3-approximation algorithm presented in \citeDBLP:journals/corr/BonnetEPS14.