The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+4 votes
534 views

02. Choose the correct alternatives (more than one may be correct) and write the corresponding letters only:

(vi) Which of the following problems is not NP-hard?

  1. Hamiltonian circuit problem
  2. The 0/1 Knapsack problem
  3. Finding bi-connected components of a graph
  4. The graph coloring problem

 

asked in Algorithms by Veteran (68.9k points)
edited by | 534 views

2 Answers

+10 votes
Best answer
  1. Is NPC and hence NP hard.
  2. Is again NP hard (optimization version is NP hard and decision version is NPC). Ref: http://stackoverflow.com/questions/3907545/how-to-understand-the-knapsack-problem-is-np-complete
  3. Is in P. See the algorithm here based on DFS: http://en.wikipedia.org/wiki/Biconnected_component
  4. NPC and hence NP hard. 
answered by Veteran (332k points)
edited by
+2 votes
Answer: C

It is in P.

A: NPC. Hence, NPH.

B: NPH.

D: NPC. Hence, NPH.
answered by Veteran (35.9k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

32,693 questions
39,293 answers
110,109 comments
36,701 users