Dark Mode

Recent questions tagged vertex-cover

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)

GO Classes asked in Graph Theory Jan 28

421 views

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

admin asked in Others Oct 23, 2022

by admin

212 views

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}?$

GO Classes asked in Graph Theory Aug 6, 2022

705 views

4 votes

2 answers

4

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.

gatecse asked in Graph Theory Sep 13, 2019

777 views

1 vote

0 answers

5

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.

Krishna Sai Vootla asked in Graph Theory Dec 29, 2018

by Krishna Sai Vootla

1.9k views

1 vote

1 answer

6

Churchill Khangar asked in Graph Theory Nov 23, 2018

by Churchill Khangar

616 views

1 vote

1 answer

7

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

Prince Sindhiya asked in Graph Theory Nov 19, 2018

by Prince Sindhiya

459 views

0 votes

1 answer

8

Discrete mathematics

Deepalitrapti asked in Graph Theory Oct 16, 2018

by Deepalitrapti

666 views

1 vote

0 answers

9

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.

Hemant Parihar asked in Graph Theory Jan 29, 2018

by Hemant Parihar

484 views

0 votes

1 answer

10

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

ashutoshsharma asked in Graph Theory Sep 21, 2017

by ashutoshsharma

389 views

1 vote

1 answer

11

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

ashutoshsharma asked in Graph Theory Sep 21, 2017

by ashutoshsharma

1.1k views

0 votes

1 answer

12

MadeEasy Subject Test: Engineering Mathematics- Graph Connectivity

vaishali jhalani asked in Graph Theory Jan 20, 2017

by vaishali jhalani

553 views

4 votes

1 answer

13

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

go_editor asked in Graph Theory Dec 29, 2016

785 views

1 vote

2 answers

14

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.

go_editor asked in Graph Theory Jun 3, 2016

584 views

To see more, click for the full list of questions or popular tags.

Recent questions tagged vertex-cover