# Questions tagged [dag]

For questions about the usage and manipulation of Directed Acyclic Graphs (DAG).

111 questions
Filter by
Sorted by
Tagged with
0answers
18 views

### Given start strings, find simplest DAG that constructs target strings by concatenation

Say we have a number of start strings (green) and a number of target strings (red). Two strings can always be concatenated to a new string which can then be arbitrarily often reused (two arrows in, (1,...
0answers
20 views

### Transitive reductions of transitive closure

Is there a name for the relationship between two DAGs A,B where B is one of the transitive reductions of the transitive closure <...
0answers
101 views

### Methods for generating DAG with small Minimum Path Cover

On a directed acyclic graph $G=(V,E)$ the Minimum Path Cover (MPC) is the minimum number of paths that can be constructed on the DAG such that all vertices are covered by at least one path. If one was ...
1answer
31 views

### Generating topological sequence from DAG with additional “not appearing before” constraints

DAG specifies the relationship of one node must appear after another. What if I add an additional constraint where one node cannot appear before another on top of the DAG? Is there an algorithm for ...
0answers
27 views

### 2 Questions about Topological sorting in DAG

$G = (V,E)$ is a directed graph without cycles (DAG). Let $s,t \in V$ two vertices in the graph such that: exists a path from $s$ to any other vertex, and exists a path from any vertex to $t$. ...
0answers
77 views

### Directed Acyclic Graph partition into minimum subgraphs with a constraint

I have this problem, not sure there is a name for it, wherein a Directed Acyclic Graph has different colored nodes. The idea is to partition it into minimum number of subgraphs with the following 2 ...
0answers
38 views

### Are these algorithms for detecting cycles in directional graph correct?

I want to detect whether a subset of a directional graph reachable from a given root has a cycle, and print some useful debug information about the cycle. It's not a problem if there's a cycle not ...
1answer
25 views

### There could not be an edge from u to v in a DAG, if w is before v in a topological order

I am trying to prove that given a DAG. There exists a valid topological ordering that has v in front of u iff there is no path from u to v. The proof is related to the fact that reverse DFS post ...
0answers
266 views

### spanning tree of a DAG (directed acyclic graph) with less forward arcs

I am new to this algorithm and graphs. Just started learning. Could someone help me which algorithm is best suited to find the spanning tree of a Directed Acyclic Graph with less forward edges?
0answers
212 views

### In a DAG, what is the name for a vertex with only one predecessor and one successor?

In a directed acyclic graph (DAG), what is the name for a vertex with only one predecessor and one successor?
0answers
27 views

### How to proof that longest path problem with weighted edges which is directed acyclic graph can provide sub optimal solution using dynamic programming [closed]

I am working on a problem which has a input as a DAG graph with non negative weights on the edges at different time points. I want to apply DFS with dynamic programming and prove that it give optimal ...