# Questions tagged [directed-graphs]

The tag has no usage guidance.

25 questions
Filter by
Sorted by
Tagged with
1answer
13 views

### Minimal cut of a directed graph such that disjoint elements are strongly connected

Given an arbitrary directed graph $G$ (which may not necessarily be connected) find a minimum set of edges $S\subseteq E$ such that every disjoint component of $G(V,E\cap S')$ is strongly connected. A ...
0answers
59 views

### Find two paths in a Graph which are disjunct in

Assuming we have two trains that start in one source edge. I want to find an algorithm that finds two paths for these trains so that they won't meet in an edge at any given time. So we have the train ...
1answer
43 views

### How to find long trails in a multidigraph

I have a directed multigraph (a multigraph is a graph that can have more than one edge between any two nodes). In Wikipedia's terminology, this is a directed multigraph (edges without own identity). I ...
1answer
188 views

### Find palindrome in directed Graph where edges are either blue or red

This is the given task: Suppose you are given an arbitrary directed graph G in which each edge is colored either red or blue, along with two special vertices s and t. Describe an algorithm that either ...
2answers
95 views

### DAG: When adding an edge that would normally result in a cycle, is there an algorithm to split the graph instead?

Summary I am using a DAG to compress a tree structure with many repeated nodes (the repeated nodes only very seldomly do not also have repeated edges out.) Normally, when attempting to add an edge to ...
0answers
22 views

### Is this a variant of “Path Covering”?

According to 1, "a path cover of a directed graph G is a set of disjoint paths in G which together contain all the vertices of G". In my research, I met a similar problem. There, you can add ...
1answer
27 views

### Transitive closure of a directed graph (reachability) algorithm intuition/explanation

Consider $n\times n$ matrix $T$ which represents transitive closure of a directed graph. That means $T_{uv}=1$ if and only if there exist a directed path between vertices $u$ and $v$. Initially, $T$ ...
0answers
16 views

### Walks on Directed graphs

Let G = (V,E) be a directed graph, where V is a finite set of nodes, and E ⊆ V × V be the set of (directed) edges (arcs). In particular, we identify a node as the initial node, and a node as the final ...
1answer
64 views

### Longest path in a strongly connected component

So if we assume that we have some strongly connected component G with n vertices. I would like to find the length of the longest path in that component. My idea is: In a strongly connected component ...
1answer
40 views

### Finding shortest path for DAG using dynamic programming vs topological sort?

Why is it that when I read about finding the shortest path for a DAG I usually just hear about topological sort? Why not use dynamic programming where the shortest path to a vertex is simply the ...
1answer
49 views

### Given an undirected graph, find an orientation such that every vertex has out-degree at least 3

Given an undirected graph $G=(V,E)$, describe an algorithm that computes an orientation of $E$ such that each vertex has out-degree at least 3. I know how to check if a vertex $v$ has at least $k$ ...
0answers
25 views

### Eliminate equal sub-paths of directed cyclic graph

Suppose we have a directed cyclic graph and a list of paths. What is the shortest way (including parallelization) of eliminating all equal paths and paths that are sub-paths of others? For example, ...
0answers
27 views

1answer
81 views

### Directed Grid Graphs; All Possible Paths Through Nodes

I have a problem in which I am interested in taking a matrix of positive integer weights, including zero, where the matrix has dimensions nrow x ncol and the columns always sum to the same arbitrary ...
1answer
349 views

### Prove finding k disjoint paths from n given paths in a directed graph is NP-complete

Problem: Given n paths in a directed graph G(V, E) and an integer k, find out k paths among them such that no two of them pass through a common node. Prove that the given problem is in NP-complete. ...