Question 15
Let G be a bipartite graph with:
• Total number of vertices = 20 • Size of maximum matching = 8
What is the size of the maximum independent set in G?
Question 15: Let G be a bipartite graph with:\ Total number of vertic…
Show answer
Correct answer: 12
Question 15 of 16 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) Quiz 1 paper sat on 15 Mar 2026, in the January 2026 term (Advanced Algorithms 15 Mar 26). It carries 3 marks.
More questions from this paper
- Figure question
- Figure question
- Figure question
- A popular conference is being held, and there are several types of seats: VIP, Regular, and Economy. Each type of seat …
- Let A be a decision problem. Suppose:\ A is in NP • A is NP-hard\ Which of the following must be true?
- Figure question
- Figure question
- Consider the following greedy approach to find the Longest Increasing Subsequence (LIS):\ Select the first element of t…
- Which of the following expressions should replace the blank( _ ) so that the algorithm correctly computes the LIS lengt…
- Figure question
- Figure question
- Which of the following expressions should replace the blank( _ ) so that the algorithm correctly computes the maximum s…
- A university wants to cover all departments {1,2,3,4,5,6,7,8,9} using the minimum number of workshops. Each workshop ca…
- Consider the following tree: What is the size of the maximum independent set of this tree?
- The value of the maximum flow in the given network is .