The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
Recent questions tagged graphalgorithms
+3
votes
0
answers
1
CMI2013B05
You are going abroad and you have to complete a number of formalities before you leave. Each task takes a full day to complete. Fortunately, you have an army of friends to help you and each task can be done by either you or any of ... . Model this problem formally using graphs. Describe an efficient algorithm for the problem and analyze the worstcase complexity of your algorithm.
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

55
views
cmi2013
descriptive
algorithms
graphalgorithms
+1
vote
1
answer
2
CMI2012B05a
Given an undirected weighted graph $G = (V, E)$ with nonnegative edge weights, we can compute a minimum cost spanning tree $T = (V, E')$. We can also compute, for a given source vertex $s \epsilon V$ , the shortest paths from s to every other vertex ... if you claim the statement is true or a counterexample if the statement is false. $T$ is still a minimum cost spanning tree of $G$.
asked
May 23, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

76
views
cmi2012
descriptive
algorithms
graphalgorithms
minimumspanningtrees
+1
vote
1
answer
3
CMI2011B05
Let $G=(V,E)$ be a undirected graph. We say $S \subseteq V$ is a clique if and only if for all $u,\: v \: \in S$, the edge $(u, v)$ is in $E$. Now let $G=(V,E)$ be a graph in which each vertex has degree at most 5. Give an algorithm to find the largest clique in $G$. What is the complexity of your algorithm?
asked
May 19, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

84
views
cmi2011
descriptive
algorithms
graphalgorithms
timecomplexity
+26
votes
4
answers
4
GATE201155
An undirected graph $G(V,E)$ contains $n \: (n>2)$ nodes named $v_1,v_2, \dots, v_n$. Two nodes $v_i, v_j$ are connected if and only if $ 0 < \mid ij\mid \leq 2$. Each edge $(v_i,v_j)$ is assigned a weight $i+j$. A sample graph with $n=4$ is shown below. The length of the path from $v_5$ to $v_6$ in the MST of previous question with $n=10$ is $11$ $25$ $31$ $41$
asked
Apr 21, 2016
in
Algorithms
by
jothee
Veteran
(
105k
points)

3.7k
views
gate2011
algorithms
graphalgorithms
spanningtree
normal
+3
votes
3
answers
5
DFS Graph
Consider vertices V1 and V2 that are simultaneously on function call stack at some point during DFS from vertex s. Which of the following are always true for this digraph ? 1. There exists a directed path from s to V1 and s to V2 . 2.There exists a directed path from ... to V2 separately then also we will have V1 and V2 simulatenously on call stack if we have a path from s to V2 via V1 .
asked
Mar 9, 2016
in
Algorithms
by
radha gogia
Loyal
(
6.4k
points)

626
views
dfs
datastructures
graphalgorithms
0
votes
0
answers
6
Complexity of Union Find Algorithm
I am referring http://www.geeksforgeeks.org/unionfind/ I am getting worst case complexity as O(V2), whereas on geeksforgeeks it is given O(ElogV). My Approach: Consider a graph 1>2>3>4>5>6>7>.......V 1+2+3+.....V = O(V2). Kindly explain with proper explanation
asked
Mar 6, 2016
in
Algorithms
by
Akshay Jindal
(
385
points)

161
views
algorithms
timecomplexity
graphalgorithms
0
votes
0
answers
7
leaf constrained minimum spanning tree
what is the suitable algorithm for the construction of leaf constrined minimum spanning tree .
asked
Feb 20, 2016
in
Programming
by
rohit kesarvani
(
5
points)

210
views
graphalgorithms
+35
votes
4
answers
8
GATE2016111
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.
asked
Feb 12, 2016
in
Algorithms
by
Sandeep Singh
Loyal
(
7.2k
points)

8k
views
gate20161
algorithms
graphalgorithms
normal
numericalanswers
+53
votes
4
answers
9
GATE2016241
In an adjacency list representation of an undirected simple graph $G=(V, E)$, each edge $(u, v)$ has two adjacency list entries: $[v]$ in the adjacency list of $u$, and $[u]$ in the adjacency list of $v$. These are called twins of each other. A twin pointer is a pointer ... list? $\Theta\left(n^{2}\right)$ $\Theta\left(n+m\right)$ $\Theta\left(m^{2}\right)$ $\Theta\left(n^{4}\right)$
asked
Feb 12, 2016
in
Algorithms
by
Akash Kanase
Boss
(
41.9k
points)

6.4k
views
gate20162
algorithms
graphalgorithms
normal
+34
votes
7
answers
10
GATE2016211
Breadth First Search (BFS) is started on a binary tree beginning from the root vertex. There is a vertex $t$ at a distance four from the root. If $t$ is the $n^{th}$ vertex in this BFS traversal, then the maximum possible value of $n$ is __________
asked
Feb 12, 2016
in
Algorithms
by
Akash Kanase
Boss
(
41.9k
points)

3.2k
views
gate20162
algorithms
graphalgorithms
normal
numericalanswers
+2
votes
1
answer
11
Ace Test Series: Algorithms  Graph Algorithms
asked
Feb 1, 2016
in
Algorithms
by
CKgurav
(
163
points)

372
views
acetestseries
algorithms
graphalgorithms
dfs
0
votes
3
answers
12
Ace Test Series: Algorithms  Graph Algorithms
Argument: As it a complete tree, maximum BFS level possible are log(n). And as BFS time is O(n+E) , taking E as path cost , it will give O(n+logn) which is O(n). So, I ticked B. Answer is given as C. But, if we take a vertex just in the first level , so the time cost will be Omega(1). So, C must not be true. Where am I going wrong??
asked
Jan 30, 2016
in
Algorithms
by
Tushar Shinde
Active
(
2.2k
points)

247
views
acetestseries
algorithms
graphalgorithms
bfs
0
votes
1
answer
13
Ace Test Series: Algorithms  Graph Algorithms
(A). When a recurrence relation has a cyclic dependency, it is impossible to use that recurrence relation (unmodified) in a correct dynamic program. (B). Given a connected graph $G(V,E)$ if a vertex $v$ $\epsilon$ $V$ is visited during ... path should have the length of atleast 'k'. Given wording is 'atmost'. So, B should be wrong. Given answer is D.
asked
Jan 30, 2016
in
Algorithms
by
Tushar Shinde
Active
(
2.2k
points)

204
views
acetestseries
algorithms
graphalgorithms
bfs
+3
votes
4
answers
14
Ace Test Series: Algorithms  Graph Algorithms
Answer is given as (B). But, shouldn't it relax point 'c' via 'a' .. So, i guess answer should be D. Is it?
asked
Jan 22, 2016
in
Algorithms
by
Tushar Shinde
Active
(
2.2k
points)

275
views
acetestseries
algorithms
graphalgorithms
dijkstrasalgorithm
+5
votes
7
answers
15
Final Analysis DIJIKSTRA ALGORITHM
Acc. to dijkstra's algorithm: What will be the shortest path from A to B ? 1) When the edge of length 15 is present. 2) when the edge of length 15 is removed.
asked
Jan 12, 2016
in
Algorithms
by
Aspi R Osa
Active
(
3.2k
points)

786
views
algorithms
graphalgorithms
multistagegraph
dynamicprogramming
+1
vote
2
answers
16
DFS
asked
Jan 8, 2016
in
DS
by
MojoJojo
Active
(
3.8k
points)

394
views
dfs
algorithms
graphalgorithms
0
votes
2
answers
17
MadeEasy Test Series: Algorithms  Graph Algorithms
Which of the following statements is/are true? S1: Dijkstra’s algorithm is not affected by negative edge weight cycles in the graph and gives correct shortest path. S2: Bellman ford algorithm finds all negative edge weight cycles present in the graph. a) Only S2 b) Only S1 c) Both S1 and S2 d) Neither S1 and nor S2
asked
Jan 2, 2016
in
Algorithms
by
Sandeep Singh
Loyal
(
7.2k
points)

681
views
algorithms
graphalgorithms
madeeasytestseries
+20
votes
4
answers
18
GATE20075
Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below. Which of the following is not a topological ordering? $1$ $2$ $3$ $4$ $5$ $6$ $1$ $3$ $2$ $4$ $5$ $6$ $1$ $3$ $2$ $4$ $6$ $5$ $3$ $2$ $4$ $1$ $6$ $5$
asked
Dec 21, 2015
in
Algorithms
by
pC
Boss
(
21.5k
points)

2k
views
gate2007
algorithms
graphalgorithms
+18
votes
2
answers
19
TIFR2015B2
Consider the following undirected connected graph $G$ with weights on its edges as given in the figure below. A minimum spanning tree is a spanning tree of least weight and a maximum spanning tree is one with largest weight. A second best minimum ... spanning tree here. There is unique minimum spanning tree, however there is more than one secondbest minimum spanning tree here.
asked
Dec 7, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
30.8k
points)

888
views
tifr2015
spanningtree
algorithms
graphalgorithms
+24
votes
4
answers
20
TIFR2014B4
Consider the following undirected graph with some edge costs missing. Suppose the wavy edges form a Minimum Cost Spanning Tree for $G$. Then, which of the following inequalities NEED NOT hold? cost$(a, b) \geq 6$. cost$(b, e) \geq 5$. cost$(e, f) \geq 5$. cost$(a, d) \geq 4$. cost$(b, c) \geq 4$.
asked
Nov 19, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
30.8k
points)

1.6k
views
tifr2014
algorithms
graphalgorithms
spanningtree
+20
votes
1
answer
21
TIFR2014B3
Consider the following directed graph. Suppose a depthfirst traversal of this graph is performed, assuming that whenever there is a choice, the vertex earlier in the alphabetical order is to be chosen. Suppose the number of tree edges is $T$, the number of back edges is $B$ and the number of cross edges is $C$. ... $B = 1$, $C = 2$, and $T = 3$. $B = 2$, $C = 2$, and $T = 1$.
asked
Nov 19, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
30.8k
points)

1.2k
views
tifr2014
algorithms
graphalgorithms
+1
vote
1
answer
22
Single source shortest path problem
asked
Nov 17, 2015
in
Algorithms
by
Payal Rastogi
Junior
(
939
points)

395
views
graphalgorithms
+6
votes
1
answer
23
TIFR2013B15
Let $G$ be an undirected graph with $n$ vertices. For any subset $S$ of vertices, the set of neighbours of $S$ consists of the union of $S$ and the set of vertices $S'$ that are connected to some vertex in $S$ by an edge of $G$. The graph $G$ has the nice property that every subset ... $O \left(\sqrt{n}\right)$ but not $O (\log n)$ $O (n)$ but not $O \left(\sqrt{n}\right)$
asked
Nov 7, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
30.8k
points)

429
views
tifr2013
graphalgorithms
unsolved
+23
votes
3
answers
24
TIFR2013B5
Given a weighted directed graph with $n$ vertices where edge weights are integers (positive, zero, or negative), determining whether there are paths of arbitrarily large weight can be performed in time $O(n)$ $O(n . \log(n))$ but not $O (n)$ $O(n^{1.5})$ but not $O (n \log n)$ $O(n^{3})$ but not $O(n^{1.5})$ $O(2^{n})$ but not $O(n^{3})$
asked
Nov 6, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
30.8k
points)

1.3k
views
tifr2013
algorithms
graphalgorithms
+11
votes
3
answers
25
TIFR2011B35
Let $G$ be a connected simple graph (no selfloops or parallel edges) on $n\geq 3$ vertices, with distinct edge weights. Let $e_{1}, e_{2},...,e_{m}$ be an ordering of the edges in decreasing order of weight. Which of the following statements ... weight spanning tree. The edge $e_{m}$ is never present in any maximum weight spanning tree. $G$ has a unique maximum weight spanning tree.
asked
Oct 24, 2015
in
Algorithms
by
makhdoom ghaya
Boss
(
30.8k
points)

580
views
tifr2011
algorithms
graphalgorithms
spanningtree
+1
vote
1
answer
26
Edge type in Undirected Graphs on Depth First Tree
Assume WHITE vertices that are yet to be discovered, BLACK vertices are finished vertices and GRAY vertices are frontier betweeen WHITE and BLACK in Depth First Search. Now, What are the various edge types like TREEEDGE and BACKEDGE possible between ... edge type between WHITE and GRAY type vertices. [ CLRS (3rd Edition) : 223:1; Page # 610 ]
asked
Oct 22, 2015
in
Algorithms
by
Salman
Junior
(
985
points)

246
views
graphalgorithms
dfs
+2
votes
1
answer
27
Do Prim’s and Kruskal’s algorithms still work if the edge weights are allowed to be negative?
asked
Oct 13, 2015
in
Algorithms
by
yes
Active
(
1.2k
points)

2k
views
shortestpath
graphalgorithms
minimumspanningtrees
+5
votes
1
answer
28
dijkstra's algo
asked
Oct 12, 2015
in
Algorithms
by
yes
Active
(
1.2k
points)

329
views
graphalgorithms
shortestpath
+4
votes
2
answers
29
What is the exact difference between prim's minimum spanning tree algorithm and dijkstra's single source shortest path algorithm?
asked
Jun 29, 2015
in
Algorithms
by
lowOnATP
(
153
points)

1.9k
views
graphalgorithms
+1
vote
2
answers
30
single source shortest path algorithm
When can we have single source shortest path algorihm runs in Big Oh of number of edges. Options are like weighted graph, undirected graph, undirected and weighted, not possilbe (i dont remember all the options)
asked
Jun 26, 2015
in
Algorithms
by
Sankaranarayanan P.N
Boss
(
11k
points)

297
views
graphalgorithms
Page:
« prev
1
2
3
4
5
6
7
8
9
next »
Quick search syntax
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
Recent Posts
ISRO CSE 2020 PAPER ANALYSE
BARC OCES/DGFS 2020
ISI CMI PDF by GATE Overflow
Calculus Important Points
Management Trainee Recruitment COAL INDIA 2020
Follow @csegate
Recent questions tagged graphalgorithms
Recent Blog Comments
100 percent
I am getting 151 marks excluding question not...
everyone will be surprised seeing the cutoff this...
There is no point of any debate/discourse here....
absolutely right
50,737
questions
57,292
answers
198,224
comments
104,909
users