Computer Sciences > GATE 2026 SET-1 > Graph Algorithms
Let G(V, E) be a simple, undirected graph. A vertex cover of G is a subset V′ ⊆ V such that for every (u, v) ∈ E, u ∈ V′ or v ∈ V′. Let the size of the smallest vertex cover in G be k. Let S be any vertex cover of size k.
For a vertex v ∈ V, which of the following constraints will always ensure that v ∈ S?
For a vertex v ∈ V, which of the following constraints will always ensure that v ∈ S?
Correct : a
Similar Questions
Let G(V,E) be an undirected and unweighted graph with 100 vertices. Let d(u,v) denote the number of edges in a shortest path between vertices u and v in V. Let...
Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant a is added to the weight of every edge. Which ONE of the foll...
Consider the following algorithm someAlgo that takes an undirected graph G as input.
The output of someAlgo (T) for the tree shown in the given figure is _____...
Total Unique Visitors
Loading......