# Questions tagged [topological-ordering]

The tag has no usage guidance.

34 questions
Filter by
Sorted by
Tagged with
468 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 ...
• 73
168 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 ...
• 163
720 views

### What don't I understand in topological sort using DFS?

Wikipedia says: The algorithm loops through each node of the graph, in an arbitrary order, initiating a depth-first search that terminates when it hits any node that has already been visited since ...
• 493
1k views

### Linear-time algorithm for determining the presence of incomparable pairs in a directed acyclic graph (DAG)

I am seeking a linear-time algorithm to determine whether a directed acyclic graph (DAG) contains at least one pair of incomparable nodes. Two nodes $u$, $v$ are said to be incomparable if there is ...
• 43
617 views

### Genetic algorithms applied to topological orderings of a DAG

I need to solve an optimization problem, whose search space is all possible topological orderings of a DAG. There is a cost function associated with each ordering, which has no simple mathematical ...
• 161
298 views

### Getting all vertices with fixed index in their topological ordering of a DAG

During my self study for graphs, I'm currently learning about topological sorting and ran into a question I'm not sure how to solve. There are typically more than one order of a topological ordering ...
• 43
222 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 ...
503 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 ...
• 115
123 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 ...
• 71
313 views

### Topological sort with minimum maximal distance in array

I have a DAG that admits many possible topological sorts. I want to construct one that has the minimum maximum distance between a node and its neighbours in an array storing the nodes in sorted order. ...
• 21
682 views

### What is the relation between Topological Sort and Strongly Connected Components?

Both the Topological Sorting algorithm and the algorithm to find Strongly Connected Components build a stack whose top is the last visited vertex. I find difficult to find an explaination because ...
• 232
3k 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 ...