Recent questions tagged vertex-cover / GATE Overflow for GATE CSE

3 votes

1 answer

1

GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 63
For an undirected graph $G$, let $\overline{G}$ refer to the complement (a graph on the same vertex set as $G$, with $(i, j)$ as an edge in $\overline{G}$ if and only if it is not an edge in $G$ ). Consider the following ... is equivalent to (iii) and (v). (i) is equivalent to (ii) and (iv). (i) is equivalent to (ii) and (v)

For an undirected graph $G$, let $\overline{G}$ refer to the complement (a graph on the same vertex set as $G$, with $(i, j)$ as an edge in $\overline{G}$ if and only if ...

GO Classes

445 views

GO Classes asked Jan 28

0 votes

0 answers

2

UGC NET CSE | October 2022 | Part 1 | Question: 56
Consider the following statements of approximation algorithm : Statement $\text{I}$: Vertex-cover is a polynomial time $2$-approximation algorithm. Statement $\text{II}$: $\text{TSP}$-tour is a polynomial time $3$-approximation algorithm for ... $\text{II}$ true Statement $\text{I}$ and Statement $\text{II}$ false

Consider the following statements of approximation algorithm :Statement $\text{I}$: Vertex-cover is a polynomial time $2$-approximation algorithm.Statement $\text{II}$: $...

admin

221 views

admin asked Oct 23, 2022

5 votes

2 answers

3

GO Classes Scholarship 2023 | Test | Question: 9
Consider the following graph $\text{G:}$ Let $\text{M, C, I, S, B, E}$ be the Matching number, chromatic number, independence number, Clique number, Vertex cover number, and edge cover number, respectively of $\text{G}.$ What is $\text{M+C+I+S+B+E}?$

Consider the following graph $\text{G:}$Let $\text{M, C, I, S, B, E}$ be the Matching number, chromatic number, independence number, Clique number, Vertex cover number, a...

GO Classes

718 views

GO Classes asked Aug 6, 2022

2 votes

1 answer

4

GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 2
The size of the minimum vertex cover of the below graph is _________

The size of the minimum vertex cover of the below graph is _________

gatecse

275 views

gatecse asked Sep 14, 2020

2 votes

1 answer

5

GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 4
In the graphs given below certain vertices are marked in RED. Which of the marked vertices form a vertex cover? (Mark all the appropriate choices)

In the graphs given below certain vertices are marked in RED. Which of the marked vertices form a vertex cover? (Mark all the appropriate choices)

gatecse

151 views

gatecse asked Sep 14, 2020

5 votes

1 answer

6

GATE Overflow Test Series | Discrete Mathematics | Test 4 | Question: 24
The number of maximum independent vertex set of the below graph is _________

The number of maximum independent vertex set of the below graph is _________

gatecse

336 views

gatecse asked Sep 14, 2020

4 votes

2 answers

7

CMI2019-A-7
An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered timings, to ensure that spectators always have some match or other available to watch. Each match ... solve? Find a minimal colouring. Find a minimal spanning tree. Find a minimal cut. Find a minimal vertex cover.

An interschool basketball tournament is being held at the Olympic sports complex. There are multiple basketball courts. Matches are scheduled in parallel, with staggered ...

gatecse

805 views

gatecse asked Sep 13, 2019

1 votes

0 answers

8

What to study & from where to study - Graph Theory for GATE 2019.
Are the following topics necessary/ apt to study for gate.(Bold items are explicitly mentioned in gate syllabus document) Connectivity Matching Coloring Cuts Covering Independent Sets Planar Graphs Isomorphism Walks, Trails, Paths, ... taking a lot of time. Can anyone please recommend a reliable and simple resource to go with.

Are the following topics necessary/ apt to study for gate.(Bold items are explicitly mentioned in gate syllabus document)ConnectivityMatchingColoringCutsCoveringIndepende...

Krishna Sai Vootla

2.0k views

Krishna Sai Vootla asked Dec 29, 2018

1 votes

1 answer

9

EET IITD

Churchill Khangar

615 views

Churchill Khangar asked Nov 23, 2018

1 votes

1 answer

10

Zeal Test Series 2019: Graph theory - Vertex Cover
is there any easy way to do this i did it by making equation,Mn+Ec=Vn, Vc+In=Vn

is there any easy way to do this i did it by making equation,Mn+Ec=Vn, Vc+In=Vn

Prince Sindhiya

466 views

Prince Sindhiya asked Nov 19, 2018

0 votes

1 answer

11

Discrete mathematics

Deepalitrapti

682 views

Deepalitrapti asked Oct 16, 2018

1 votes

0 answers

12

MadeEasy Test Series: Graph Theory - Vertex Cover
Vertex cover = Total vertex - Maximum independent set vertex cover = 8 - 3 = 5. In given answer Covering number is given as 4. I think it is given wrong please verify. Thank you.

Vertex cover = Total vertex - Maximum independent setvertex cover = 8 - 3 = 5.In given answer Covering number is given as 4. I think it is given wrong please verify. Than...

Hemant Parihar

494 views

Hemant Parihar asked Jan 29, 2018

0 votes

1 answer

13

DISCRETE
The size of minimum vertex cover can be - (A) Smaller than the size of maximum matching (B) No smaller than the size of maximum matching (C) Cannot say

The size of minimum vertex cover can be - (A) Smaller than the size of maximum matching (B) No smaller than the size of maximum matching (C) Cannot say

ashutoshsharma

396 views

ashutoshsharma asked Sep 21, 2017

1 votes

1 answer

14

discrete
Given a maximum matching M, if we pick one endpoint of each edge in M, this form a valid vertex cover. TRUE FALSE

Given a maximum matching M, if we pick one endpoint of each edge in M, this form a valid vertex cover. TRUE FALSE

ashutoshsharma

1.1k views

ashutoshsharma asked Sep 21, 2017

0 votes

1 answer

15

MadeEasy Subject Test: Engineering Mathematics- Graph Connectivity

vaishali jhalani

557 views

vaishali jhalani asked Jan 20, 2017

4 votes

1 answer

16

TIFR CSE 2016 | Part B | Question: 10
A $vertex \: cover$ in an undirected graph $G$ is a subset $ C \subseteq V(G)$ such that every edge of $G$ has an endpoint in $C$. An independent set in $G$ is a subset $I \subseteq V(G)$ such that no edge has both its endpoints in $I$. Which of the ... $\mid C \mid \: \: \geq \: \: \mid V(G)\mid /2$ $C$ intersects every independent set

A $vertex \: cover$ in an undirected graph $G$ is a subset $ C \subseteq V(G)$ such that every edge of $G$ has an endpoint in $C$. An independent set in $G$ is a subset $...

go_editor

815 views

go_editor asked Dec 29, 2016

1 votes

2 answers

17

ISI2011-PCB-CS-3c
A vertex cover of a graph $G = (V, E)$ is a set of vertices $V' \subseteq V$ such that for any edge $(u, v) \in E$, either $u$ or $v$\ (or both) is in $V'$. Write a linear time algorithm to find the minimum vertex cover of a given tree $T$. Establish its correctness.

A vertex cover of a graph $G = (V, E)$ is a set of vertices $V' \subseteq V$ such that for any edge $(u, v) \in E$, either $u$ or $v$\ (or both) is in $V'$. Write a linea...

go_editor

601 views

go_editor asked Jun 3, 2016

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