Dark Mode

Recent questions tagged topological-sort

1 vote

1 answer

31

Madeasy 2k17
Caption

kamakshi asked in Algorithms Nov 18, 2017

1.3k views

3 votes

1 answer

32

topological ordering of DAG
What is the method to find no of topological ordering of a Directed Acyclic Graph? For an instance, i found two graphs on internet, whose no of topological ordering is given but how to quickly calculate the total no of ordering? Graph 1 For graph 1, no of ... . If I try to solve it by brute force method, then it's taking lot's of time. Is there any faster way?

stanchion asked in DS Oct 21, 2017

965 views

0 votes

0 answers

33

Topological sorting
My ques. is not the no. of topological sort as i have computed it myself. My problem is can someone please telll me a efficient approach as tree method is taking a lot of time here, like by use of combinatorics, can we find it easily, i.e in less time. and if possible, pls provide general approach apart from tree method.

mohit chawla asked in Algorithms Feb 3, 2017

by mohit chawla

2.2k views

3 votes

5 answers

34

MadeEasy CBT 2017: Algorithms - Graph Algorithms
No of topological sortings

Vasu_gate2017 asked in Algorithms Jan 22, 2017

by Vasu_gate2017

2.1k views

0 votes

1 answer

35

Number of possible conflict equivalent serial schedules
"Number of possible conflict equivalent serial schedules to some non-serial schedule is total number of topological sorts of its precedence graph." I haven't read this method anywhere yet but I found it by myself while ... answer, please can anyone refer me to standard(reference) books about this!(I found that,too but failed)

smartmeet asked in Databases Jan 17, 2017

1.0k views

0 votes

1 answer

36

topological sort
how many topological sort possible for n vetex(except the null graph)???

Hira Thakur asked in Algorithms Nov 29, 2016

699 views

1 vote

0 answers

37

MIT QUIZs 2009
Topological sort can be performed using one breadth-first search procedure on the graph?? ans) False. why? as both are DFS and BFS can do it in O(v+e) time

2018 asked in Algorithms Nov 23, 2016

by 2018

438 views

2 votes

1 answer

38

Algo-Topological Sort

KISHALAY DAS asked in Algorithms Nov 14, 2016

by KISHALAY DAS

1.8k views

3 votes

0 answers

39

topological sort
Pls find the answer and verify ???? 1)14 as 9!/3!3!3! 2) 36 as 3!*3! 3)216 as 3!*3!*3!

Amit puri asked in Algorithms Aug 3, 2016

831 views

61 votes

5 answers

40

GATE CSE 2016 Set 1 | Question: 11
Consider the following directed graph: The number of different topological orderings of the vertices of the graph is _____________.

Sandeep Singh asked in Algorithms Feb 12, 2016

by Sandeep Singh

28.3k views

2 votes

2 answers

41

Topology
How many topological sorts of the following directed graph are possible?

shivanisrivarshini asked in Algorithms Jan 7, 2016

by shivanisrivarshini

1.3k views

21 votes

7 answers

42

GATE CSE 2007 | Question: 5
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$

pC asked in Algorithms Dec 21, 2015

by pC

7.7k views

0 votes

2 answers

43

What is the difference between Topological sort and bellman-ford Algorithm ?
A) Do following for every vertex u in topological order. ..Do following for every adjacent vertex v of u if (dist[v] > dist[u] + weight(u, v)) dist[v] = dist[u] + weight(u, v ... following similar steps , so then why is the time complexity of bellman-ford O(VE) while for toplogical sort it is O(V+E) ?

radha gogia asked in Algorithms Jul 5, 2015

1.3k views

0 votes

1 answer

44

What is the maximum number of topological sorting possible ?
For a given set of vertices , can we compute the maximum number of topological sortings possible ?

radha gogia asked in Algorithms Jun 30, 2015

1.3k views

31 votes

5 answers

45

GATE CSE 2014 Set 1 | Question: 13
Consider the directed graph below given. Which one of the following is TRUE? The graph does not have any topological ordering. Both PQRS and SRQP are topological orderings. Both PSRQ and SPRQ are topological orderings. PSRQ is the only topological ordering.

go_editor asked in Algorithms Sep 26, 2014

7.6k views

Page:

Recent questions tagged topological-sort