The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+5 votes

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?

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

+11 votes

Best answer

- Is NPC and hence NP hard.
- 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
- Is in P. See the algorithm here based on DFS: http://en.wikipedia.org/wiki/Biconnected_component
- NPC and hence NP hard.

- All categories
- General Aptitude 1.2k
- Engineering Mathematics 4.9k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 949
- Others 1.3k
- Admissions 408
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,780 questions

41,757 answers

118,924 comments

41,399 users