# Questions tagged [directed-graphs]

The tag has no usage guidance.

39 questions
Filter by
Sorted by
Tagged with
55 views

### Find a simple path from S to T in a directed graph so that the product of its weights is maximum

I'm looking for an algorithm that finds a simple path from S to T in a directed graph (which might have cycles) so that the product of edge weights in the path is maximum. All the edge weights of the ...
• 23
36 views

### Is there a name for a directed graph where we cannot re-enter a vertex that we leave (to a different vertex)?

I am wondering if there is an "official" name for a directed graph where we cannot re-enter a vertex once we leave it to a different vertex. Here's an example of one such graph, where once ...
21 views

### Edmond's theorem for k-disjoint arborescences in digraphs

Recently while studying arborescences in graph theory, I came across Edmond's theorem for $k$ edge-disjoint arborescences in digraphs if a finite digraph is $k$ edge-connected from a vertex r for ...
88 views

### Find all nodes in directed graph from starting node that complete a loop

Suppose I have a directed graph, where one of the nodes is selected to be the "initial" node. What algorithms should I consider using to to find all the nodes that have a path from the ...
• 101
81 views

### Find most vertices in a directed tree where no path of length less than 3 connects any pair

Given a directed tree $T = (V, E)$, we need to find a set of vertices $A \subseteq V$ such that for every two vertices $v,u \in A$ either there is no path between them or the path between them is of ...
• 456
1 vote
130 views

### How to find lightest path in directed weighted graph where each edge has a color

We're Given a directed graph $G = (V, E)$ and a weight function $\omega : E \rightarrow \mathbb{Z}$. Each edge is colored with one of these colors: Red, Green, Blue. Given two vertices $s,t \in V$, ...
• 456
26 views

### Symmetry group of the acyclic oriented L-cube using the Hyperoctahedral group

I'm trying to figure out all elements of a symmetry group for the acyclic oriented $L$-cube. I do have an algorithm, but its complexity is not suitable for larger $L$. I computed $L=5$ on my old ...
• 1
15 views

### --Graphical Models-- Understanding blocked paths and conditional independence

I am quite confused by this slide from a course I found on the internet from UCL on Graphical Models. Here is the slide: I would like to confirm whether I have correct understanding: In the following ...
• 155
49 views

### Find the directed subgraph with least edges that preserves connectivity

I have a directed graph $G$ with a set of nodes $N$ and a set of edges $E$ with the following property : if $(A\to B)\in E$ and $(B\to C)\in E$, then $(A\to C)\in E$, for all nodes $A,B,C$. I would ...
1 vote
28 views

### Is the first distance that gets assigned to a node in BFS always the shortest distance?

Consider the following bfs pseudo code that calculates distances of all nodes from $s$ in graph $G=(V,E)$. I know that if $G$ was undirected and unweighted, then the above bfs would calculate correct ...
• 113
224 views

### Shortest walk with alternating colors in a directed graph

Let $G$ be a directed graph such that every edge is colored (red, yellow or green). I want to compute the shortest walk (possibly with repeated vertices) with the restriction that the colors are ...
• 115
75 views

### Connectivity in Directed Graph

Connectivity in undirected graph can be easily identified using Disjoint Union Set (Union Find). Is there any way to check connectivity in a directed graph efficiently other than doing Depth First ...
376 views

### Maximum number of distinct nodes that can be visited on a single walk

Given a directed graph which may contain cycles, how can I find the maximum number of distinct nodes that can be visited on a single walk? I have done some research and the most similar-sounding ...
• 133
46 views

### Iterative version of depth-first-search code to detect cycle in a directed graph [duplicate]

I have solved a problem that required me to find if the given directed graph had a cycle or not. The deal is, I used a recursive approach to solve it in the depth-first-search method. I was just ...
31 views

### Given a vertex in a digraph, is there a standard term for (the vertices reachable from it) union (the vertices reaching it)?

Question in title. Looking for whether there is a term that is, if not widely understood, at least citeable to a source. This is equivalent to asking for the set of nodes that are comparable to the ...
• 3,413
1 vote
45 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 ...
1 vote
74 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 ...
102 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 ...
510 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 ...
148 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 ...
34 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 ...
• 239
41 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$ ...
19 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 ...
1 vote
219 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 ...
• 27
218 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 ...
• 113
1 vote
130 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$ ...
• 231
31 views

• 1
1 vote