Vertex Cover In Bipartite Graph

Vertex Cover Problem (VCP):  Given a graph G=(V, E) , Find minimum number of vertices that cover all the edges i.e., a set V' \subseteq V of  such that \left|{V'}\right| is minimum and for every edge at least one end point belongs to V'.

Weighted Vertex Cover Problem (WVCP): Given a graph G=(V, E) and a cost function \omega : V \rightarrow R^+, Find minimum weight vertex set that cover all the edges i.e., a set V' \subseteq V of  such that \omega(V') = \sum_{v \in V'} \omega(v) is minimum and for every edge at least one end point belongs to V'.

Bipartite Graph: A Graph whose vertex set is partitioned into two sets  A and  B  where each edge joins a vertex in  A to a vertex in   B.

Integer Program for VCP: For each  vertex v \in V, take a variable x_v. Now define x_v = 1 if vertex v is in our solution and  x_v = 0 otherwise. Therefore the integer program (IP) for  VCP  is as follows:

min \sum_{v \in V}x_v

s.t. x_u + x_v \geq 1 for all e = (u,v) \in E

x_v \in \{0, 1\} for all v \in V

vc

Advertisements
This entry was posted in Uncategorized. Bookmark the permalink.

One Response to Vertex Cover In Bipartite Graph

  1. Pingback: Local Limits | Eventually Almost Everywhere

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s