Questions tagged [topological-ordering]
The topological-ordering tag has no usage guidance.
14
questions
0
votes
2answers
17 views
Valid orderings for topological sort
I am reading Algorithms by Dasgupta et al and the graph section provides an example graph and mentions that there are 4 orderings with one of them being B, A, D, C, E, F.
Are the other 3?
B, A, D, C,...
2
votes
2answers
93 views
Ordering of operations in a DAG of git commits
Context: I'm looking for a better state resolution algorithm for https://github.com/MichaelMure/git-bug
Summary of the current algorithm and shortcomings
git-bug is a distributed bug-tracker that ...
2
votes
1answer
31 views
Modified topological sort
I recently asked a related question at the theoretical CS stack exchange, but I have modification to the problem that I think is a bit tougher. This seems like a better place anyways.
Let's define a &...
1
vote
0answers
20 views
Proof that “the last vertex in any postordering (in a DFS) of G lies in a source component of G”
From the book Algorithms (Jeff Erickson), there's a lemma that states:
The last vertex in any postordering of G lies in a source component
of G
My initial reaction to this was that the proof would ...
6
votes
5answers
240 views
How to edge-color a directed acyclic graph so that every path visits none or all edges of each color?
Given a directed acyclic graph $G$ and a start vertex $s$ and an end vertex $e$, consider a coloring of the edges valid if, for every path from $s$ to $e$ and every color $c$, either $c$ is never ...
1
vote
0answers
34 views
Optimally find one of the total orderings for a poset based on some metadata about the elements
Given a finite, partially ordered set with the following two properties:
Every element in the set has one of two types: "A" or "B". The type does not define the total ordering of the set and is ...
0
votes
1answer
68 views
Is topological sort of an original graph same as post-ordering dfs of its transpose graph
I have an intuition that topo-sort of an original graph
A -> B -> C
D -> B
topo-sort is [D, A, B, C] or [A, D, B, C]
If I transpose the graph
<...
1
vote
0answers
14 views
Shortest sequence of jobs, with dependencies, subject to capacity constraints
Suppose I have $n$ courses, some with some prerequisites, and I can take up to $k$ courses in a semester. I want to compute the least number of semesters needed to complete all courses, while ...
0
votes
1answer
181 views
Why do we do topological sorting to find shortest or longest path in weighted DAG?
I was wondering why do we need to do the topological sort before performing relaxing of edges.
Wouldn't it'd be better if we do :
if starting vertex is "s"
...
3
votes
1answer
283 views
Construct a DAG from given multiple topological orderings
I need to construct a DAG, from its given topological orderings (i.e. the graph $G$ created must have all the orderings given as its topological orderings). For simplicity, the vertices are labeled as ...
5
votes
1answer
111 views
Is there an algorithm to minimize working set during a topological traversal?
I have a dependency graph of tasks, which forms a DAG. I'm looking for an algorithm to calculate the optimal topological traverse to minimize the "working set". Specifically, I define the current ...
1
vote
1answer
688 views
Determine whether there exists a path in a directed acyclic graph that reaches all nodes without revisiting a node
For this I came up with a DFS recursion.
Do DFS from any node and keep doing it until all nodes are Exhausted. I.E. pick the next unvisited node once you cannot keep recursing.
The element with ...
3
votes
0answers
94 views
Order the vertices to maximize the weights of edges in the induced subgraph
I have a complete directed graph $G:=(V,E)$ with directed edge weights $c_{ij}$ for every distinct nodes $i$ and $j$.
Goal: Find the topological order such that the smallest edge weight of the ...
0
votes
1answer
34 views
Topological Ordering
I have learnt to solve topological ordering using $in-degree$ method where we have to take the vertices having in-degree $0$ at an instance and arrange them in that order.
For example consider ...
