Questions tagged [directed-graphs]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
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 ...
1
vote
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 ...
2
votes
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 ...
3
votes
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 ...
2
votes
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 ...
2
votes
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 ...
0
votes
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$ ...
0
votes
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 ...
1
vote
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 ...
0
votes
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 ...
1
vote
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$ ...
0
votes
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, ...
0
votes
0answers
27 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\...
0
votes
0answers
85 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 ...
1
vote
1answer
12 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 ...
0
votes
1answer
37 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 ...
0
votes
1answer
72 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 ...
0
votes
0answers
105 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 ...
0
votes
0answers
55 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
0answers
18 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 ...
0
votes
0answers
201 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 ...
0
votes
1answer
29 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 ...
0
votes
1answer
62 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
vote
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 ...
4
votes
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. ...