Scribd
Upload
4 views17 pages

Daa Module 5

The document discusses NP-hard graph problems, specifically the Clique Decision Problem and the Node Cover/Vertex Cover Problem, detailing their definitions and optimization strategies. It outlines steps and algorithms for solving the Node Cover problem, emphasizing the importance of finding the smallest set of vertices to cover all edges. Additionally, it briefly mentions job shop scheduling without providing further details.

Uploaded by

divya.vyshu91
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views17 pages

Daa Module 5

The document discusses NP-hard graph problems, specifically the Clique Decision Problem and the Node Cover/Vertex Cover Problem, detailing their definitions and optimization strategies. It outlines steps and algorithms for solving the Node Cover problem, emphasizing the importance of finding the smallest set of vertices to cover all edges. Additionally, it briefly mentions job shop scheduling without providing further details.

Uploaded by

divya.vyshu91
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

DIGITAL NOTES

ON
DESIGN AND ANALYSIS OF ALGORITHMS

[Link] II YEAR - II SEM


(2023-24)

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING

MALLA REDDY ENGINEERING COLLEGE


NP-hard graph problems:

 CDP(clique decision problem).

 Node cover/vertex cover problem.

 The Clique decision Problem: It has vertices and edges where each vertex is
connected to every other vertex.

Clique: The sub graph of a graph which is complete graph.

Clique Decision problem: Stating the answer as yes(or)no based on the existence of
clique of size “k” then it is a decision problem.

Clique Optimization problem: An optimization problem is of finding the best solution


from all feasible solution.

 In figure(1) it contains clique of size 2 and 3 so here it is a decision problem due to


presence of clique and also optimization problem due max size(3).

 In figure (2) it has clique of size 2,3 and 4, so it is a decision problem and
optimization due to max size of(4).
 Node cover/Vertex Cover Problem:

Given a graph, find the smallest set of vertices such that each edge of the graph is
incident to at least one vertex in the set.

Steps:

1. Find a vertex “v” with maximum degree.

2. Add “v” to the solution and remove “v” and all its incident edges from
graph.

3. Repeat until all edges are covered

Algorithm:

Approx-Vertex-Cover (G = (V, E))

C = empty-set;

E'= E;

While E' is not empty do


{

Let (u, v) be any edge in E': (*)

Add u and v to C;

Remove from E' all edges incident to

u or v;

Return C;

(b,c,f,g) is a feasible solution of size 4 which covers all edges

(b,e,d) is the optimal solution which has size=3 and covers all the edges.
Job shop scheduling:

You might also like