Suggest a Book

# Vertex cover in bipartite graphs

Level: unknown

posted Sep 11 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

The Vertex Cover of a graph $G(V,E)$ is a set of vertices $S \subseteq V$ such that each edge of the graph is incident to at least one vertex of the set $S$.

Minimum cost vertex cover : Given a graph $G(V,E)$ and a cost function on the vertex set $V$, find a minimum cost vertex cover in $G$.

• Formulate Minimum cost vertex cover as an integer program (IP).

• When $G$ is a bipartite graph, prove that the constraint matrix of this IP is totally unimodular. Hence conclude that the natural linear programming relaxation of this IP is integral, implying that Minimum Weighted vertex cover is polynomially solvable on bipartite graphs.

Source: folklore
delete retag edit

## Stats

Posted: Sep 11 '12

Seen: 116 times

Last updated: Sep 11 '12