Matching and vertex cover in bipartite graphs
Lists
Only you see this
Abstract
In this chapter we consider two very closely related problems, maximum weighted matching and minimum cost vertex cover in bipartite graphs. Linear programming duality plays a crucial role in understanding the relationship between these problems. We will show that the natural linear programming relaxations for both the matching problem and the vertex cover problem are integral, and then use duality to obtain a min–max relation between them. Nevertheless, our proofs of integrality use the iterative method by arguing the existence of 1-elements in an extreme point solution.
BibTeX
@inproceedings{lau2011matching,
author = {Lap Chi Lau and R. Ravi and Mohit Singh},
title = {{Matching and vertex cover in bipartite graphs}},
booktitle = {Cambridge},
year = {2011},
doi = {10.1017/cbo9780511977152.004},
}Loading related content...