Questions tagged [directed-graphs]
The directed-graphs tag has no usage guidance.
51
questions
1
vote
1
answer
31
views
Minimum edges removed to turn a strongly connected graph into an acyclic graph
If I start with a directed graph that is strongly connected, is there a straightforward way / algorithm to find the smallest set of edges to remove, such that the result is a directed but acyclic ...
0
votes
0
answers
26
views
Is the min-cut size of a directed graphs transpose the same as that of the original?
I was wondering whether the transpose of graph maintains the same size of the minimal cut in a directed graph (digraph).
This may be trivial as I haven't been able to find anything here or on Google ...
4
votes
3
answers
969
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
0
votes
1
answer
20
views
Balanced Directed Graph Realization
I have a list of integers: each integer represents a node in a directed graph, and the value of the integer is both the desired indegree and outdegree of said node.
Some research suggests that this is ...
- 103
0
votes
0
answers
56
views
How to divide weakly connected graph into "k" weakly connected subgraphs (using e.g. networkx)?
I have a weakly-connected weighted digraph $G$, and I'd like to divide it into $k$ weakly connected subgraphs $G_k$ each with approximate equal total weight $w_{T_k}$ ($w_{T_k}$ = sum of weights of ...
- 11
1
vote
1
answer
30
views
What is a good heuristic for multi-point A* on a directed graph?
I am conducting a stateful search of a large graph in an effort to find some solutions of minimal cost. With an admissible heuristic for estimated time to completion from a given state (as in A*), I ...
- 11
5
votes
2
answers
631
views
Structural equivalence of self-referential structures
Given two types, T1 and T2, how does structural equivalence work when they're self-referential? Further, how do we go about proving it?
...
- 59
2
votes
1
answer
175
views
Turning an undirected graph into a directed graph such that in-degree of all nodes is at most 1 or show it is not possible
I was thinking what if you just started with the node with lowest non-zero degree $u$ (only count undirected edges) and picked random edge that is connected to that and direct that inwards. EX: ...
- 21
0
votes
1
answer
37
views
Which algorithm solves the single-pair shortest path in a weighted directed cyclic graph?
I need to find the shortest path between two nodes in a directed, positively weighted graph that migt contain cycles. All weights are either zero or one. If it was not weighted, I'd use breadth-first ...
- 3
1
vote
2
answers
267
views
Algorithm for finding a path in a directed graph that visits each node in a given subset
I was wondering about a solution for the following problem:
Given a directed graph $G=(V,E)$ and a subset of vertices $U \subseteq V$ suggest an algorithm that finds if there is a directed path that ...
- 229
1
vote
1
answer
116
views
(Directed) Graphs: Minimal Vertices Subset With No Outgoing Edges
I've been trying to study some graph algorithms and, as part of it, prove a bunch of graph theorems in order to practice my ability to do theoretical work with graphs.
Specifically, I've been trying ...
- 113
0
votes
0
answers
24
views
Maximize flow through a graph, where edges can be added subject to restrictions
I'm doing a course in algorithms and I'm stuck on this problem.
Given a set of vertices on a grid. Every vertex has a coordinate (x,y).
An source and a sink has ...
- 103
0
votes
1
answer
33
views
Directed graph of bank balances and transactions, how to process transactions?
I'm working on a game where there are several different entities represented by nodes. Each node has a starting balance, and directed edges show where money is owed from one account to another.
One ...
- 25
0
votes
2
answers
325
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 ...
- 133
0
votes
0
answers
38
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 ...
- 1
2
votes
0
answers
50
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 ...
- 53
0
votes
1
answer
407
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
0
votes
1
answer
107
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 ...
- 453
1
vote
1
answer
337
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$, ...
- 453
0
votes
0
answers
30
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 ...
- 31
2
votes
1
answer
104
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 ...
- 123
1
vote
1
answer
89
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
0
votes
1
answer
361
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
0
votes
1
answer
335
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 ...
- 15
3
votes
1
answer
683
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
0
votes
0
answers
130
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 ...
2
votes
0
answers
37
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,453
1
vote
1
answer
203
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 ...
- 13
0
votes
0
answers
95
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 ...
2
votes
1
answer
189
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 ...
- 201
3
votes
1
answer
673
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 ...
user136953
2
votes
2
answers
287
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 ...
- 133
2
votes
0
answers
54
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
0
votes
1
answer
55
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$ ...
0
votes
0
answers
36
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 ...
user132357
1
vote
1
answer
405
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
-1
votes
1
answer
420
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 ...
- 111
2
votes
1
answer
283
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$ ...
- 241
0
votes
0
answers
31
views
length of longest representative "uu" in suffix automaton
Trying to find the length of the longest representative of an equivalence class in suffix automaton, such that it has the form:
$\{v\in{}\Sigma|v$ is the longest representative $\wedge$ $(\exists{}u\...
- 1
0
votes
0
answers
150
views
What's the fastest time complexity algorithm for finding maximal paths in an unweighted directed graph?
I see a lot of interest online to the problems of finding shortest paths, longest paths, and all simple paths. I'm interested in implementing a state-of-the-art algorithm to find all (simple) maximal ...
- 125
1
vote
1
answer
21
views
Circular path visiting fewest nodes
I don't know what this problem is called, so I haven't been able to Google for it, but I have a graph problem that I feel must have been solved many times before, and I just cannot find a good ...
- 181
0
votes
1
answer
194
views
Number of spanning arborescences with a specific root in a directed graph
I am wondering how to calculate the number of spanning arborescences in a directed graph when a root is specified. For example:
where there are 5 spanning arborescences. Note that there is an edge ...
- 131
0
votes
1
answer
245
views
Does every DAG have at most one "universal source"?
A "universal source" in a directed graph is a vertex v for which out-deg(v)=n-1 and in-deg(v)=0.
I know that any DAG has at least one source but can it have more than one for a universal?
I ...
- 3
0
votes
0
answers
131
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 ...
- 92
0
votes
0
answers
215
views
Graph algorithm to group nodes by level and group size
I have a directed graph representing some topics organized as follows (below screenshot is a subset of the graph):
I'm looking for an algorithm to group a set of nodes (in blue in the diagram) ...
1
vote
0
answers
19
views
finding common navigational paths / central nodes within a graph
I have a directed weighted graph representing street (edges weighted by distance) and street intersections (nodes).
Using this graph, I would like find central nodes that a person might find ...
- 111
0
votes
0
answers
364
views
Removing any arbitrary vertex from a directed graph?
I came upon this particular question which I do not understand from Jeff E. Algorithms, Chapter 9, ex. 8. https://jeffe.cs.illinois.edu/teaching/algorithms/book/09-apsp.pdf
How can we remove any ...
- 23
0
votes
1
answer
154
views
The definition of a graph's transitive reduction
I want to determine the transitive reduction of this graph:
as of now, I only found the first step of doing this: represent the transitive closure of the graph as an adjacency relation, so this is ...
- 11
0
votes
1
answer
132
views
Algorithm for display nodes of a particular node based on in-degree and out-degree
Suppose we have following directed graph. When I click on say node $e$, it should make in-degree and out-degree of node $e$ and connected nodes red. As shown in Resulting Graph. My purpose is, when I ...
- 1
1
vote
1
answer
144
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 ...
- 11