Questions tagged [dag]
For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).
9
questions
2
votes
1
answer
233
views
Topological sorting and NP-hard proof
I meet a problem. I can find a sub-optimal solution, but cannot find an optimal one and cannot prove its NPC hardness.
The problem can also be described as follows. Given a sequence $X=\{x_1,x_2,...,...
- 31
16
votes
4
answers
12k
views
Transitive reduction of DAG
I am looking for O(V+E) algorithm for finding the transitive reduction given a DAG.
That is remove as many edges as possible so that if you could reach v from u, for arbitrary v and u, you can still ...
- 291
3
votes
1
answer
186
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 ...
- 33
3
votes
1
answer
129
views
Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?
There is an unsorted list of $n$ items $x_1, \ldots, x_n$. Until you can sort the list, you are given one of the ${n \choose 2}$ possible binary comparisons uniformly at random (with replacement).
On ...
- 512
3
votes
1
answer
204
views
Number of states in an AND-OR DAG
Consider a DAG of $N$ nodes, where each node can take on one of two value, either false, $0$ or true, $1$. Additionally, let each non-leaf nodes (nodes with parents) be assigned a type: either an AND ...
- 371
2
votes
1
answer
3k
views
Counting number of paths between two vertices in a DAG
I need an algorithm that computes the number of paths between two nodes in a DAG (Directed acyclic graph) I need a dynamic porgramming solution if possible.
- 1,331
1
vote
1
answer
154
views
Traversing a directed graph with negative weights
Let $G = (V, E)$ be a directed graph with negative edge weights and no cycles, and $L:V \to \mathbb [0, \infty[$ be a function defined over this graph. This graph represents all possible paths a ...
- 115
1
vote
0
answers
519
views
Obtaining a graph with no cycles after removing k edges
I am looking for an algorithm that upon an input of a directed graph G and a natural number k,outputs a set of k edges, that upon removing them, the graph will have no cycles. If there are no such k ...
- 73
-1
votes
2
answers
4k
views
Longest path in DAG or finding DAG diameter
A directed acyclic graph (DAG), is a directed graph with no directed cycles.
That is, it consists of vertices and edges, with each edge directed from one vertex to another, such that there is no way ...
- 159