Questions tagged [topological-ordering]
The topological-ordering tag has no summary.
40 questions
1
vote
1
answer
145
views
Given a tree, find a preorder-like ordering which satisfies additional ordering between nodes
Suppose you have this tree:
0
/ \
1 3
| |
2 4
/ \
5 6
With preorder-like ordering I mean the orderings where the father ...
- 11
1
vote
1
answer
124
views
Enumerate all implication chains in a graph that reach a certain node
In the context of my research, I am having a hard time in solving this problem. It resembles the topological ordering problem, but since that the graph can contain cycles, I cannot apply the existing ...
- 11
1
vote
1
answer
128
views
Using bit strings for modeling stable hierarchies in tables, is the faster solution?
Purely relational databases (SQL) seem to suffer to nowadays from the lack of a good solution for search/indexing hierarchies. Here a systematic review of the subject: https://stackoverflow.com/q/...
- 151
1
vote
1
answer
266
views
How to count the number of topological sorts in a directed acyclic graph with multiple roots
I have a task to count the number of possible topological sorts, and it is known that the graph has N vertices and N-1 edges, and the edges are also given.
For example:
N = 4
1 2
1 3
4 3
For this ...
- 13
0
votes
1
answer
55
views
What is the time complexity of determine_build_order function below?
Problem statement: Find out the order in which projects should be build such that dependencies are built first. Dependencies are represented using a list of pairs of projects, where the second project ...
- 15
1
vote
2
answers
108
views
Random directed acyclic graph (Barak-Erdös): find "upstream" vertices
The problem
Consider a set of $N$ vertices $V=\{v_1,v_2,...,v_N\}$. We define a random directed acyclic graph by the set of edges $E$ as follows: for every $i<j$, $e_{ij}:=(v_i\rightarrow v_j) \in ...
- 73
3
votes
1
answer
153
views
Finding maximal elements of a partially ordered set
My problem
Given a partially-ordered set $(S, <)$, I want to compute the set of maximal elements
$$
S_{max} =\{a\in S | \nexists b \in S, a < b \}
$$
while making as few comparisons as possible ...
- 73
5
votes
1
answer
874
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 ...
- 523
0
votes
2
answers
382
views
Find minimum of a function only knowing the ordering of a set of input points
Suppose I have a function $f: \mathbb{R}^n\rightarrow\mathbb{R}$. All I know about the function is, I have a set of pairs of vectors ($\vec{v}_a$, $\vec{v}_b$) for which I know which one is greater (i....
- 9
1
vote
0
answers
99
views
Total combinations in DAG with upper bound on node value
There is a directed acyclic graph with M edges. There is only one component (If they were undirected edges all nodes will be reachable will from one to another). An edge from a to b means value of ...
2
votes
1
answer
107
views
Algorithm to identify common subsets
Given a large dataset $D$ and multiple sets of filters that can be applied to $D$, e.g.
$setA = \{filterOnColorRed\}$
$setB = \{filterOnAgeGreaterThan20\}$
$setC = \{filterOnColorRed, ...
- 121
4
votes
3
answers
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
1
vote
0
answers
144
views
Topological sort of DAG that minimizes maximum number of unique-source-edges crossing through any node when placed in 1-d line
Consider a DAG such as one shown below:
How do I find a particular topological order of nodes, such that when the nodes are placed in a straight line, the maximum number of unique-edges that cross ...
- 292
1
vote
2
answers
532
views
Why compute finish time in topological sort
In depth first search each vertex can be associated with a discovery time and a finish time. I am reading the following implementation of topological sort in terms of depth first search
...
- 11
1
vote
1
answer
535
views
Checking if there exists a 'source' vertex
In a directed graph $G=(V,E)$ we denote a vertex $s\in V$ to be a 'source' if there exists in $G$ a path from $s$ to all other vertices $u \in V$.
The problem asks for an efficient algorithm to return ...
- 377