Find the size of the minimum size vertex cover, that is, cardinality of a vertex cover with minimum cardinality, for an undirected connected graph with V vertices and m edges.

Examples:

Input: V = 6, E = 6 6 / / 1 -----5 /|\ 3 | \ \ | \ 2 4 Output: Minimum vertex cover size = 2 Consider subset of vertices {1, 2}, every edge in above graph is either incident on vertex 1 or 2. Hence the minimum vertex cover = {1, 2}, the size of which is 2. Input: V = 6, E = 7 2 ---- 4 ---- 6 /| | 1 | | \| | 3 ---- 5 Output: Minimum vertex cover size = 3 Consider subset of vertices {2, 3, 4}, every edge in above graph is either incident on vertex 2, 3 or 4. Hence the minimum size of a vertex cover can be 3.http://www.geeksforgeeks.org/finding-minimum-vertex-cover-graph-using-binary-search/

Civil Lab Equipment Manufacturer offer a comprehensive range of oil and petroleum testing lab equipments, which are widely used in Schools, Colleges and Universities.

ReplyDeleteMob: +91-9891445495, +91-8448366515, +918587026175

Phone : +91-11-23657121

Website : http://civillabequipmentmanufacturer.com, http://setestindia.com