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
+23
votes
3
answers
1
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.2k
points)

4.5k
views
gate2007
algorithms
graphalgorithms
easy
+30
votes
7
answers
2
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.2k
points)

3.2k
views
gate2004
algorithms
graphalgorithms
normal
+23
votes
2
answers
3
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.2k
points)

2.6k
views
gate2004
algorithms
graphalgorithms
normal
+35
votes
4
answers
4
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.2k
points)

4.6k
views
gate2003
algorithms
graphalgorithms
normal
+52
votes
4
answers
5
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.2k
points)

5.6k
views
gate2003
algorithms
graphalgorithms
normal
+17
votes
3
answers
6
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.2k
points)

1.8k
views
gate2003
algorithms
graphalgorithms
normal
+40
votes
5
answers
7
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)

6.7k
views
gate2006
algorithms
graphalgorithms
easy
+18
votes
3
answers
8
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.2k
points)

1.5k
views
gate2002
algorithms
graphalgorithms
timecomplexity
normal
descriptive
+26
votes
6
answers
9
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.2k
points)

2.8k
views
gate2001
algorithms
graphalgorithms
normal
+19
votes
3
answers
10
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.2k
points)

1.4k
views
gate2000
algorithms
easy
graphalgorithms
+35
votes
5
answers
11
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.2k
points)

6.1k
views
gate2008
algorithms
graphalgorithms
normal
+19
votes
3
answers
12
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.2k
points)

2.3k
views
gate2008
normal
algorithms
graphalgorithms
+17
votes
3
answers
13
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.2k
points)

2.7k
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
ECIL Interview Experience
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
Follow @csegate
Recent questions tagged graphalgorithms
Recent Blog Comments
Not really. It was excluding shipping I guess....
Ok sir. Actually pricing on Flipkart is 200 less...
NO.
Is this application open for 2020 graduates i.e....
@Ayush Upadhyaya sir any approximate idea...
50,645
questions
56,601
answers
195,854
comments
102,228
users