GATE CSE 2006 | GATE CSE Year Wise Previous Years Questions

GATE CSE

PREVIOUS NEXT

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Let SHAM₃ be the problem of finding a Hamiltonian cycle in a graph G = (V, E) with |V| divisible by 3 and DHAM₃ be the problem of determining if a Hamiltonian cycle exists in such graphs. Which one of the following is true?

Both DHAM₃ and SHAM₃ are NP-hard

SHAM₃ is NP-hard, but DHAM₃ is not

DHAM₃ is NP-hard, but SHAM₃ is not

Neither DHAM₃ nor SHAM₃ is NP-hard

GATE CSE 2006

MCQ (Single Correct Answer)

-0.3

Let S be an NP-complete problem and Q and R be two other problems not known to be in NP. Q is polynomial time reducible to S and S is polynomial-time reducible to R. Which one of the following statements is true?

R is NP-complete

R is NP-hard

Q is NP-complete

Q is NP-hard

GATE CSE 2006

MCQ (Single Correct Answer)

-0.6

Consider the following graph: GATE CSE 2006 Algorithms - Greedy Method Question 29 English

Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal’s algorithm?

$$(a-b),(d-f),(b-f),(d-c),(d-e)$$

$$(a-b),(d-f),(d-c),(b-f),(d-e)$$

$$(d-f),(a-b),(d-c),(b-f),(d-e)$$

$$(d-f),(a-b),(b-f),(d-e),(d-c)$$

GATE CSE 2006

MCQ (Single Correct Answer)

-0.3

To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is:

Queue

Stack

Heap

B-Tree

PREVIOUS NEXT

GATE CSE Papers

2024