Register

GATE-2012
closed

• closed by
563 views
1 votes
1 votes
closed with the note: https://gateoverflow.in/786/gate2012_29

Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weight of edges in G.Let T and T' be the minimum spanning trees of G and G' respectively with total weights t and t'. Which of the following statements is true?

a) T'=T with total weight t'=t^2

b)T'=T with total weight t'

c)T' !=T but total weight t'=t^2

d)None of the above

• closed by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

72 votes
72 votes
14 answers
2
gatecse asked Sep 26, 2014
28,955 views
GATE CSE 2012 | Question: 39
A list of $n$ strings, each of length $n$, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is $O (n \log n) $ $ O(n^{2} \log n) $ $ O(n^{2} + \log n) $ $ O(n^{2}) $
A list of $n$ strings, each of length $n$, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is$O (n \log...
User Avatar
59 votes
59 votes
5 answers
3
gatecse asked Sep 15, 2014
16,489 views
GATE CSE 2012 | Question: 29
Let $G$ be a weighted graph with edge weights greater than one and $G'$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T'$ be the minimum spanning trees of $G$ and $G'$, respectively, with total weights $t$ ... $t' < t^2$ $T' \neq T$ but total weight $t' = t^2$ None of the above
Let $G$ be a weighted graph with edge weights greater than one and $G'$ be the graph constructed by squaring the weights of edges in $G$. Let $T$ and $T'$ be the minimum ...
User Avatar
42 votes
42 votes
4 answers
4
gatecse asked Aug 5, 2014
14,419 views
GATE CSE 2012 | Question: 18
Let $W(n) $ and $A(n)$ denote respectively, the worst case and average case running time of an algorithm executed on an input of size $n$. Which of the following is ALWAYS TRUE? $A(n) = \Omega (W(n))$ $A(n) = \Theta (W(n))$ $A(n) = \text{O} (W(n))$ $A(n) = \text{o} (W(n))$
Let $W(n) $ and $A(n)$ denote respectively, the worst case and average case running time of an algorithm executed on an input of size $n$. Which of the following is ALWA...
User Avatar
Link Copied!