search
Log In

Recent questions tagged graph-algorithms

4 votes
1 answer
1
We have a Directed Graph with 100 vertexes. v1 --> v2 --> ... v100 and all edges weights is equal to 1. we want to used bellman-ford for finding all shortest paths from v1 to other vertexes. this algorithm in each step check all edges in arbitrary order. if in ... is the minimum and maximum of steps in this problem? ُSolution says 2 and 100. anyone can say how the min and max steps is calculated?
asked Jul 10, 2016 in DS Sara Nimlon 610 views
3 votes
2 answers
2
Algorithm which solves the all pair shortest path problem is A)Dijkstra's algorithm B)Floyd's algorith C)Prim's algorithmm D)Warshall's algorithm
asked Jun 24, 2016 in DS vivekpinto07 4.2k views
11 votes
3 answers
3
Djikstra’s algorithm is used to Create LSAs Flood an internet with information Calculate the routing tables Create a link state database
asked Jun 10, 2016 in Algorithms jothee 3.5k views
0 votes
3 answers
4
Someone claims that Kruskal's algorithm for finding minimum spanning tree can return different spanning trees for the same input graph $G$. Do you agree with the claim? If so, why? If not, argue briefly why the claim is incorrect.
asked Jun 8, 2016 in Algorithms jothee 268 views
1 vote
1 answer
5
Let $G = (V, E)$ be an undirected weighted graph with all edge weights being positive. Design an efficient algorithm to find the maximum spanning tree of $G$.
asked May 31, 2016 in Algorithms jothee 337 views
5 votes
1 answer
6
Given an undirected weighted graph $G = (V, E)$ with non-negative 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 ... you claim the statement is true or a counterexample if the statement is false. All the shortest paths from $s$ to the other vertices are unchanged.
asked May 27, 2016 in Algorithms jothee 502 views
3 votes
0 answers
7
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 your ... constraints. Model this problem formally using graphs. Describe an efficient algorithm for the problem and analyze the worst-case complexity of your algorithm.
asked May 23, 2016 in Algorithms jothee 105 views
1 vote
1 answer
8
Given an undirected weighted graph $G = (V, E)$ with non-negative 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 in ... argument 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 jothee 139 views
1 vote
1 answer
9
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 jothee 142 views
31 votes
5 answers
10
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 i-j\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 jothee 6.1k views
3 votes
3 answers
11
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 V1 to ... s 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 radha gogia 759 views
0 votes
0 answers
12
I am referring http://www.geeksforgeeks.org/union-find/ 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 Akshay Jindal 203 views
0 votes
0 answers
13
what is the suitable algorithm for the construction of leaf constrined minimum spanning tree .
asked Feb 20, 2016 in Programming rohit kesarvani 283 views
43 votes
4 answers
14
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.
asked Feb 12, 2016 in Algorithms Sandeep Singh 13.8k views
62 votes
4 answers
15
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 from an ... 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 Akash Kanase 9.5k views
39 votes
8 answers
16
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 Akash Kanase 5.3k views
0 votes
3 answers
18
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 Tushar Shinde 389 views
0 votes
1 answer
19
(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 level $K$ of a breadth ... every other possible 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 Tushar Shinde 300 views
3 votes
4 answers
20
5 votes
7 answers
21
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 Aspi R Osa 1.2k views
1 vote
2 answers
22
DFS
asked Jan 8, 2016 in DS Mojo-Jojo 509 views
0 votes
2 answers
23
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 Sandeep Singh 735 views
20 votes
5 answers
24
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 pC 3.4k views
26 votes
2 answers
25
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 ... minimum spanning tree here. There is unique minimum spanning tree, however there is more than one second-best minimum spanning tree here.
asked Dec 7, 2015 in Algorithms makhdoom ghaya 1.5k views
28 votes
4 answers
26
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 makhdoom ghaya 2.7k views
23 votes
1 answer
27
Consider the following directed graph. Suppose a depth-first 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$ ... $T = 3$. $B = 1$, $C = 2$, and $T = 3$. $B = 2$, $C = 2$, and $T = 1$.
asked Nov 19, 2015 in Algorithms makhdoom ghaya 2.2k views
1 vote
1 answer
28
6 votes
1 answer
29
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 of ... $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 makhdoom ghaya 543 views
28 votes
3 answers
30
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 makhdoom ghaya 2.1k views
...