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 mst
0
votes
0
answers
1
max weighted MST possible
Let G be a complete undirected graph on 5 vertices 10 edges, with weights being 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Let X be the value of the maximum possible weight a MST of G can have. Then the value of x will be_____ the answer to this question is given as 11 but there is no procedure given . Please ,can anyone help me out in understanding the procedure
asked
Jan 26, 2019
in
Graph Theory
by
Nandkishor3939
Active
(
1.3k
points)

125
views
mst
0
votes
0
answers
2
Ace Test Series: Algorithms  Minimum Spanning Tree
asked
Jan 4, 2019
in
Algorithms
by
jhaanuj2108
(
197
points)

62
views
acetestseries
algorithms
mst
0
votes
0
answers
3
AlgorithmMETestMST
A Spanning tree T(V,E) has bottleneck edge, means all edges present in T with the greatest cost would be bottleneck edges. Now they have said, A spanning tree T of G is a minimum bottleneck spanning tree if no spanning tree T' existed with cheaper ... I think if in (A) it was minimum bottleneck spanning tree, then (B) would not have been possible to produce. Please guide.
asked
Nov 17, 2018
in
Algorithms
by
Ayush Upadhyaya
Boss
(
29k
points)

114
views
algorithms
mst
0
votes
0
answers
4
Find the weight MST
Let us assume that $G$($V$, $E$) is a weighted complete graph such that weight of the edge <$V_K$,$V_L$>=2$K$$L$. The weight MST of $G$ with 100 vertices is ____________________.
asked
Nov 10, 2018
in
Algorithms
by
Naveen Kumar 3
Boss
(
15.4k
points)

98
views
algorithms
mst
0
votes
0
answers
5
Minimum spanning tree implementation in other way
Which algorithm will be implemented on the weighted graph in which the edges are uniformly distributed over the halfopen interval $[0,1)$ to construct MST so that it runs in linear time? $A)$ Kruskal's algorithm $B)$ Prim's algorithm $C)$ Both $(A)$ and $(B)$ $D)$ None of these
asked
Nov 10, 2018
in
Algorithms
by
Lakshman Patel RJIT
Veteran
(
58.5k
points)

107
views
algorithms
graphalgorithms
minimumspanningtrees
mst
0
votes
1
answer
6
Self doubt Spanning tree
How many numbers of spanning tree are possible?
asked
Nov 9, 2018
in
Algorithms
by
Lakshman Patel RJIT
Veteran
(
58.5k
points)

257
views
algorithms
mst
minimumspanningtrees
+1
vote
1
answer
7
Kruskal Algorithm
Complexity of Kruskal's algorithm for finding the minimum spanning tree of an undirected graph containing n vertices and m edges if the edges are unsorted is _______ ______________________________________________________________________________ If elements are sorted we do with Union Find algo with ... is $log^{*}V$ Now from here can we derive it for unsorted edges? for ref: here
asked
Jun 30, 2018
in
Algorithms
by
srestha
Veteran
(
118k
points)

223
views
algorithms
mst
kruskalsalgorithm
–1
vote
1
answer
8
Ace Test Series: Algorithms  Minimum Spanning Trees
asked
Jun 29, 2018
in
Algorithms
by
Na462
Loyal
(
7k
points)

131
views
acetestseries
algorithms
mst
+2
votes
1
answer
9
Minimum Spanning Tree
1) Kruskal Algorithm 2) Prims Algorithm 3) Dijkstra Algorithm 4) Bellman Ford Algorithm 5) Floyd Warshall Algorithm Among these which one works for only i) Positive edge weight ii) Negative edge weight iii) Negative weight cycle
asked
Apr 30, 2018
in
Algorithms
by
srestha
Veteran
(
118k
points)

323
views
minimumspanningtrees
algorithms
graphalgorithms
mst
0
votes
3
answers
10
#Algorithms #MST Doubt in MST Questions.
Question 1) The shortestpath tree computed by Dijkstra's algorithm is necessarily an MST? Question2 ) Prim's algorithm works with negative weighted edges?
asked
Apr 29, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

153
views
algorithms
mst
graphalgorithms
0
votes
1
answer
11
SELF_DOUBT(MST)
What important point we keep in mind while finding the #(number) of spanning tree ?? from the given graph
asked
Apr 29, 2018
in
Algorithms
by
air1ankit
Active
(
4.6k
points)

76
views
algorithms
mst
graphconnectivity
0
votes
1
answer
12
#Algorithms #MST No of MST's possible?
In a connected weighted graph with n vertices, all the edges have same positive integer weights. Then, the maximum number of minimum weight spanning trees in the graph is? My take  If it's a cyclic graph and just with one cycle in G then we will get, ... cycle (and it's not a complete Graph) then you get more than n MST's where n is the number of nodes in G.
asked
Apr 28, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

102
views
algorithms
mst
0
votes
2
answers
13
#Algorithms #MST Self Doubt.
Let G be a connected simple graph with non distinct edge weights. Now, e be the lightest edge in G. So, does this edge e is present in every MST of G? My take  when all edge weights are same then lightest edge e won't be there.
asked
Apr 28, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

60
views
algorithms
mst
0
votes
1
answer
14
#Algorithms #MST Variance of Gate 2018 MST Question.
Original question  https://gateoverflow.in/204122/gate201847 Consider the following undirected graph G: Choose a value for x that will minimize the number of minimum weight spanning trees (MWSTs) of G. The number of MWSTs of G for this value ... would be what would be minimum value of x for which we get minimum MST's then x=1 would be correct.
asked
Apr 28, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

149
views
algorithms
mst
0
votes
1
answer
15
#Algorithms #Mst Reference to Gate 2008 Question
Link to actual Question  https://gateoverflow.in/3355/gate2008it45?show=214096#c214096 For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Spanning ... before (c,f) which is 3 and that makes it false b/c (c,f) should be chosen first.
asked
Apr 25, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

91
views
algorithms
mst
0
votes
1
answer
16
#Algorithms MST Question.
A complete, undirected, weighted graph G is given on the vertex {0,1,…,n−1} for a fixed ‘n=4’. Draw the minimum spanning tree of G if the weight of the edge (u,v) is ∣u−v∣ the weight of the edge (u,v) is u+v
asked
Apr 23, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

119
views
mst
algorithms
+1
vote
1
answer
17
#Algorithms MST Question Doubt
Let G be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is decreased by the same value (constraint is  keeping all edge positive all the time), then is it TRUE or FALSE? Shortest path between any pair of vertices does not change?
asked
Apr 11, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

200
views
algorithms
timecomplexity
mst
0
votes
0
answers
18
#Algorithms Kruskal Algorithm for MST Doubt.
Time Complexity of Kruskal  O(mlogm + n.O(1) + m.logn) mlogm > for sorting edges in increasing order. n.O(1) > n UNIONS as we've n nodes in G and each takes O(1) m.logm > Find operation takes logn time as height of tree can never ... as we have m edges in G. Now my doubt is  is it O(mlogm) or O(mlogn)? I know, given is O(mlogn), but how?
asked
Apr 11, 2018
in
Algorithms
by
iarnav
Loyal
(
8.4k
points)

96
views
algorithms
timecomplexity
mst
+1
vote
0
answers
19
Minimum Spanning Tree Problem
Given a graph with positive and distinct edge weights. If I double or triple.. the edge weights then: 1. Shortest path will remain same 2. Mst will remain same Right? Note : Here i am doubling or tripling or four times ..... not increasing by +c
asked
Feb 19, 2018
in
Algorithms
by
Na462
Loyal
(
7k
points)

243
views
minimumspanningtrees
algorithms
mst
graphalgorithms
+3
votes
1
answer
20
#distinct MSTs
......................................................
asked
Jan 28, 2018
in
Algorithms
by
Tuhin Dutta
Boss
(
10.5k
points)

201
views
algorithms
mst
spanningtree
+1
vote
0
answers
21
gate 2007
can option c also be false,here in the question it is not mentioned that graph has distinct weight so if all have same weight then there may be chance that option c might be false?plsss clarify? Let w be the minimum weight among all edge weights in an ... T, all edges have the same weight. Every minimum spanning tree has an edge of weight w e is present in every minimum spanning tree
asked
Jan 26, 2018
in
Algorithms
by
Rajeev Kumar 1
(
57
points)

55
views
mst
+2
votes
0
answers
22
Minimum Spanning tree
Kindly justify with an example
asked
Jan 15, 2018
in
Algorithms
by
Pawan Kumar 2
Active
(
4.2k
points)

79
views
mst
+2
votes
0
answers
23
Minimum Spanning Tree
Which of the following are correct for Minimum Spanning Tree from graph G with unique weights, with the weight function w: E→R (more than one possible) If we divide all weights by some non zero value MST will be unchanged (answer for both positive ... ) If we add or subtract all weights by some number MST will remain unchanged. (answer for both positive and negative values)
asked
Dec 25, 2017
in
Algorithms
by
smsubham
Boss
(
11.4k
points)

137
views
algorithms
minimumspanningtrees
mst
graphalgorithms
+2
votes
1
answer
24
Minimum Spanning tree
If a simple undirected graph with positive weighted edges has 10 vertices and 30 edges, such that the cost of the Minimum Spanning tree is 59. Now, if all the edges weights are increased by 2, then the cost of the new MST is
asked
Dec 13, 2017
in
Algorithms
by
VIKAS TIWARI
Junior
(
727
points)

308
views
algorithms
minimumspanningtrees
mst
0
votes
2
answers
25
Minimum Spanning Tree
Multiplying all edge weights by a positive number(>1) will always change the cost of minimum spanning tree. True/False
asked
Dec 8, 2017
in
Algorithms
by
VS
Boss
(
10.8k
points)

563
views
algorithms
mst
0
votes
1
answer
26
Test Series
Are MST and shortest path tree identical? T/F? with reasoning.
asked
Dec 5, 2017
in
Algorithms
by
targate2018
Active
(
1.8k
points)

63
views
graph
graphtheory
mst
minimumspanningtrees
+1
vote
0
answers
27
MST Kruskal
First statement is False because complexity will be O(E2). I think the second statement is true? But not sure
asked
Nov 2, 2017
in
Algorithms
by
Shivam Chauhan
Loyal
(
8.9k
points)

149
views
algorithms
mst
timecomplexity
primsalgorithm
+2
votes
1
answer
28
Kruskal
Can Anyone provide all the data structure that we can used and time complexity that we get for Kruskal algorithm of finding the minimum spanning tree.
asked
Oct 29, 2017
in
Algorithms
by
junaid ahmad
Loyal
(
8.6k
points)

108
views
algorithms
mst
+1
vote
1
answer
29
Algorithm kruskal algorithm MST
Which algorithm does kruskal uses for detecting every cycle and what is the time complexity?
asked
Sep 27, 2017
in
Algorithms
by
rahul sharma 5
Boss
(
25.5k
points)

173
views
algorithms
timecomplexity
mst
+3
votes
2
answers
30
MST..
Let G(V, E) be an undirected graph with positive edge weights. What is the worst case time complexity to find minimum spanning tree using Kruskal algorithm is implemented using array data structure ? a) O(E+V log V) b) O(V log V) c) O(V2) d) O(V log2V)
asked
Jan 16, 2017
in
Algorithms
by
srestha
Veteran
(
118k
points)

122
views
mst
algorithms
Page:
1
2
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
Management Trainee Recruitment COAL INDIA 2020
ECIL Interview Experience
Follow @csegate
Recent questions tagged mst
Recent Blog Comments
it's depends year to year
What was the average cutoff that was maintained...
@Shivateja MST I don't think it will go high
http://univ.tifr.res.in/gs2020/Test_Results/INT_Sh...
TIFR interview shortlist is published.
50,741
questions
57,244
answers
198,016
comments
104,608
users