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
+27
votes
7
answers
1
GATE200582a
Let $s$ and $t$ be two vertices in a undirected graph $G=(V,E)$ having distinct positive edge weights. Let $[X,Y]$ be a partition of $V$ such that $s \in X$ and $t \in Y$. Consider the edge $e$ having the minimum weight amongst all those edges that have one ... tree of $G$ the weighted shortest path from $s$ to $t$ each path from $s$ to $t$ the weighted longest path from $s$ to $t$
asked
Sep 22, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

3.1k
views
gate2005
algorithms
graphalgorithms
normal
+34
votes
1
answer
2
GATE200538
Let $G(V,E)$ be an undirected graph with positive edge weights. Dijkstra’s single source shortest path algorithm can be implemented using the binary heap data structure with time complexity: $O\left(V^2\right)$ $O\left(E+V\log V\right)$ $O\left(V\logV\right)$ $O\left(\left(E+V\right)\logV\right)$
asked
Sep 22, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

4.8k
views
gate2005
algorithms
graphalgorithms
normal
+32
votes
4
answers
3
GATE200913
Which of the following statement(s) is/are correct regarding BellmanFord shortest path algorithm? P: Always finds a negative weighted cycle, if one exists. Q: Finds whether any negative weighted cycle is reachable from the source. $P$ only $Q$ only Both $P$ and $Q$ Neither $P$ nor $Q$
asked
Sep 22, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

5.2k
views
gate2009
algorithms
graphalgorithms
normal
+23
votes
4
answers
4
GATE200741
In an unweighted, undirected connected graph, the shortest path from a node $S$ to every other node is computed most efficiently, in terms of time complexity, by Dijkstra’s algorithm starting from $S$. Warshall’s algorithm. Performing a DFS starting from $S$. Performing a BFS starting from $S$.
asked
Sep 22, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

4.8k
views
gate2007
algorithms
graphalgorithms
easy
+34
votes
7
answers
5
GATE200481
Let $G_1=(V,E_1)$ and $G_2 =(V,E_2)$ be connected graphs on the same vertex set $V$ with more than two vertices. If $G_1 \cap G_2= (V,E_1\cap E_2)$ is not a connected graph, then the graph $G_1\cup G_2=(V,E_1\cup E_2)$ cannot have a cut vertex must have a cycle must have a cutedge (bridge) has chromatic number strictly greater than those of $G_1$ and $G_2$
asked
Sep 19, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

3.5k
views
gate2004
algorithms
graphalgorithms
normal
+25
votes
2
answers
6
GATE200444
Suppose we run Dijkstra’s single source shortest path algorithm on the following edgeweighted directed graph with vertex $P$ as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are finalized? $P,Q,R,S,T,U$ $P,Q,R,U,S,T$ $P,Q,R,U,T,S$ $P,Q,T,R,U,S$
asked
Sep 19, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

2.8k
views
gate2004
algorithms
graphalgorithms
normal
+36
votes
4
answers
7
GATE200370
Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_{k+1}) \in E$ for all $k$ in $i$ through $j1$. A simple path is a path in which no ... path length from $j$ to $k$ If there exists a path from $j$ to $k$, every simple path from $j$ to $k$ contains at most $A[j,k]$ edges
asked
Sep 17, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

5.1k
views
gate2003
algorithms
graphalgorithms
normal
+54
votes
4
answers
8
GATE200367
Let $G =(V,E)$ be an undirected graph with a subgraph $G_1 = (V_1, E_1)$. Weights are assigned to edges of $G$ as follows. $w(e) = \begin{cases} 0 \text{, if } e \in E_1 \\1 \text{, otherwise} \end{cases}$ A singlesource shortest path algorithm is ... of edges in the shortest paths from $v_1$ to all vertices of $G$ $G_1$ is connected $V_1$ forms a clique in $G$ $G_1$ is a tree
asked
Sep 17, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

6.3k
views
gate2003
algorithms
graphalgorithms
normal
+17
votes
3
answers
9
GATE200321
Consider the following graph: Among the following sequences: abeghf abfehg abfhge afghbe Which are the depthfirst traversals of the above graph? I, II and IV only I and IV only II, III and IV only I, III and IV only
asked
Sep 16, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

2k
views
gate2003
algorithms
graphalgorithms
normal
+42
votes
5
answers
10
GATE200612
To implement Dijkstra’s shortest path algorithm on unweighted graphs so that it runs in linear time, the data structure to be used is: Queue Stack Heap BTree
asked
Sep 16, 2014
in
Algorithms
by
Rucha Shelke
Active
(
3.3k
points)

7.5k
views
gate2006
algorithms
graphalgorithms
easy
+18
votes
3
answers
11
GATE200212
Fill in the blanks in the following template of an algorithm to compute all pairs shortest path lengths in a directed graph $G$ with $n*n$ adjacency matrix $A$. $A[i,j]$ equals $1$ if there is an edge in $G$ from $i$ to $j$, and $0$ otherwise. ... line containing the blanks in the Algorithm step and fill in the blanks. Fill in the blank: The running time of the Algorithm is $O$(___).
asked
Sep 16, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

1.6k
views
gate2002
algorithms
graphalgorithms
timecomplexity
normal
descriptive
+26
votes
6
answers
12
GATE20012.14
Consider an undirected, unweighted graph $G$. Let a breadthfirst traversal of $G$ be done starting from a node $r$. Let $d(r,u)$ and $d(r,v)$ be the lengths of the shortest paths from $r$ to $u$ and $v$ respectively in $G$. If $u$ is visited before $v$ during the breadthfirst traversal, ... is correct? $d(r,u) < d(r,v)$ $d(r,u) > d(r,v)$ $d(r,u) \leq d(r,v)$ None of the above
asked
Sep 15, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

3.1k
views
gate2001
algorithms
graphalgorithms
normal
+20
votes
3
answers
13
GATE20001.13
The most appropriate matching for the following pairs $\begin{array}{ll}\hline \text{X: depth first search} & \text{1: heap } \\\hline \text{Y: breadth first search} & \text{2: queue} \\\hline \text{Z: sorting} & \text{3: stack} \\\hline \end{array}$ is: $\text{X  1, Y  2, Z  3}$ $\text{X  3, Y  1, Z  2}$ $\text{X  3, Y  2, Z  1}$ $\text{X  2, Y  3, Z  1}$
asked
Sep 14, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

1.5k
views
gate2000
algorithms
easy
graphalgorithms
+38
votes
6
answers
14
GATE200845
Dijkstra's single source shortest path algorithm when run from vertex $a$ in the above graph, computes the correct shortest path distance to only vertex $a$ only vertices $a, e, f, g, h$ only vertices $a, b, c, d$ all the vertices
asked
Sep 12, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

6.7k
views
gate2008
algorithms
graphalgorithms
normal
+19
votes
3
answers
15
GATE200819
The Breadth First Search algorithm has been implemented using the queue data structure. One possible order of visiting the nodes of the following graph is: $MNOPQR$ $NQMPOR$ $QMNPRO$ $QMNPOR$
asked
Sep 12, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

2.6k
views
gate2008
normal
algorithms
graphalgorithms
+17
votes
3
answers
16
GATE20087
The most efficient algorithm for finding the number of connected components in an undirected graph on $n$ vertices and $m$ edges has time complexity $\Theta(n)$ $\Theta(m)$ $\Theta(m+n)$ $\Theta(mn)$
asked
Sep 11, 2014
in
Algorithms
by
Kathleen
Veteran
(
52.3k
points)

3k
views
gate2008
algorithms
graphalgorithms
timecomplexity
normal
Page:
« prev
1
...
4
5
6
7
8
9
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
PSUs Recruitment
ISRO Recruitment
BARC Recruitment
GATE CSE: All NITs Admissions
GATE CSE: IIT Hyderabad Admissions
Follow @csegate
Recent questions tagged graphalgorithms
Recent Blog Comments
Here is a poll on ISRO marks, you can say your...
They removed it,please create some poll or...
Did not find... post the link here
Please update your marks in gate overflow fb...
For CIL
50,834
questions
57,853
answers
199,514
comments
108,382
users