This is a mathematical structure composed of a set of points or vertices and a set of connectors or edges. The edges connect the vertices and those vertices are directed. Also no cycles or in other words a directed edge that connects a vertex to a vertex are disallowed.
4
votes
0answers
249 views
Multiple-sources dominator trees: compact representation and fast algorithm?
I recently learnt about the concept of dominator trees and was fascinated by it.
I was wondering how the problem extends to computing dominators from multiple sources, or even from all vertices in ...
1
vote
0answers
131 views
Dynamic shortest path data structure for DAG
Let $G$ be a dynamic DAG (directed acyclic graph) where new vertices and new edges can be inserted.
I am looking for an efficient data structure/algorithm to maintain the shortest path from a fixed ...
5
votes
1answer
115 views
Canonical labeling of special classes of DAGs
Graph Isomorphism of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known.
What are some special classes of DAGs that can be ...
3
votes
1answer
150 views
Breadth first search and Eppstein K shortest paths algorithm
I'm trying to understand the algorithm for finding K shortest paths in a graph described by Eppstein in this paper: http://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf
I have trouble particularly ...
5
votes
1answer
161 views
Revision Tracking Graph
Define the Revision Tracking Graph (RTG), which is an oriented graph (without circles) where each node x has a set C(x) associated with it. C(x) contains all edges on all paths from a node 0 ( C(0) = ...
21
votes
0answers
544 views
Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?
Roughly speaking, my question is:
How costly is to make a cyclic graph
acyclic while preserving all simple $s$-$t$ paths?
Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$.
...
13
votes
1answer
443 views
Exact Algorithm for edge labeling problem in DAG
I am implementing some system part of which requires some help. I am therefore framing it as a graph problem to make it domain independent.
Problem: We are given directed acyclic graph $G=(V,E)$. ...
13
votes
1answer
789 views
Finding k shortest Paths with Eppstein's Algorithm
I'm trying to figure out how the Path Graph $P(G)$ according to Eppstein's Algorithm in this paper works
and how I can reconstruct the $k$ shortest paths from $s$ to $t$ with the corresponding heap ...
9
votes
3answers
338 views
Efficient DAG comparison over a network
In distributed version control systems (such a Mercurial and Git) there is a need to efficiently compare directed acyclic graphs (DAGs). I'm a Mercurial developer, and we would be very interested in ...
2
votes
0answers
191 views
Recursive parallel topological sorting in linear time
While doing some research on topological sorting I came across a paper Parallel Topological Sorting Algorithm, TADA, A. and MIGITA, M. and NAKAMURA, R. which claims a recursive divide-and-conquer ...
0
votes
0answers
375 views
Cycles in a directed graph
Wondering if we can prove the following or if it is already proved where can I get the proof.
Let $v_1, v_2, v_3, \ldots, v_n$ and $t$ be $n+1$ vertexes in a directed graph. $v_1, v_2, v_3, \ldots, ...
3
votes
1answer
213 views
measures for a DAG (directed acyclic graph)?
Recently, I want to devise some kernelization (in the framework of parameterized complexity) for problem on DAG. So, find a proper parameter is essential.
Well, is there a measure for the importance ...
3
votes
1answer
178 views
Shortest path in a DAG consisting of multiple copies of a smaller DAG
Let's say we have $k$ weighted DAGs (directed acyclic graphs)
$$H_1 = (V_1, A_1), \dots, H_k = (V_k, A_k)$$
that are copies of one another. Now consider another weighted DAG $G$ that is built by ...
5
votes
0answers
174 views
Restricted Reachability Problem
Let $G$ be a directed acyclic graph with $V$ vertices and $E$ edges. Choose some subset of $n\leq V$ "special" vertices $\{v_i\}_{i=1}^n$. How efficiently can we preprocess $(G, \{v_i\})$ so that we ...
4
votes
3answers
468 views
A possibly new representation of DAGs
I had an idea for a way of representing DAGs, it's very easy to explain:
Each node in the DAG is given an array of n integers. If it is possible to traverse from A to B then each of B's integers must ...
3
votes
1answer
218 views
Finding common label sequences in a directed acyclic graph
I have a directed acyclic graph with ~250k nodes, each node has one of about 100 symbols as label. Letting a word be the sequence of n symbols that corresponds to a path containing n nodes in the ...
13
votes
2answers
250 views
Does an algorithm exist to efficiently maintain connectedness information for a DAG in presence of inserts/deletes?
Given a directed acyclic graph, $G(V,E)$, is it possible to efficiently support the following operations?
$isConnected(G,a,b)$: Determines if there is a path in $G$ from node $a$ to node $b$
...
4
votes
2answers
185 views
Generation of unlabeled acyclic digraphs
I'm looking for an algorithm to efficiently generate all unlabeled acyclic digraphs of a given order. (By "unlabeled" I mean that no two of the generated digraphs should be isomorphic.)
Thanks
Edit: ...
8
votes
3answers
501 views
Route existence between n pairs of nodes
Given a directed acyclic graph with $2n$ nodes how can one determine if there is a path between any of following n pairs of nodes $(1 \rightarrow n+1), \ldots, (n \rightarrow n+n)$? There is a simple ...
7
votes
2answers
481 views
Testing/Identifying a Topological Sorting
You're given a set of $n$ Directed Acyclic Graphs $G_1, G_2, ..., G_n$ over the same set of $m$ vertices $V$. You're also given a permutation of the set of vertices $(v_1,v_2,...,v_m)$. What is the ...
-4
votes
1answer
352 views
Compact representation of DAG,
Given a DAG (which represents DDG – each node is a operation the in-edge/s show the operands from which inputs are taken) I want to obtain its compact representation of the graph, in such a way that:
...
1
vote
2answers
151 views
Special Properties Of DAWGs with Unique Elements
A DAWG is a specialized form of a Directed Acyclic Graph. Admittedly, not terribly specialized. I was wondering if DAWGs built from proper sets (unique, sorted) had any special properties? It seems ...
5
votes
2answers
697 views
Number of reachable vertices in DAG for every vertex
Let $G(V,E)$ be an acyclic directed graph, such that out-degree of any vertex is $O(\log{|V|})$. For every vertex of $G$ we can count the number of reachable vertices, just by running dfs from every ...
1
vote
0answers
840 views
DAG partitioning to subgraphs
Given a DAG with $|V| = n$ and has $s$ sources, we have to present subgraphs such that each subgraph has approximately $k_1=\sqrt{s}$ sources and approximately $k_2=\sqrt{n}$ nodes.
(Note: ...
10
votes
4answers
512 views
Directed NP-hard problems on DAGs
Tree width measures how close a graph is to a tree. Several NP-hard problems are tractable on graphs with bounded tree width. If a problem remains NP-hard on trees then tree width cannot save us. This ...
11
votes
1answer
490 views
Positive topological ordering, take 2
This is a followup to David Eppstein's recent question and is motivated by the same problems.
Suppose I have a dag with real-number weights on its vertices. Initially, all of the vertices are ...
37
votes
5answers
1k views
Positive topological ordering
Suppose I have a directed acyclic graph with real-number weights on its vertices. I want to find a topological ordering of the DAG in which, for every prefix of the topological ordering, the sum of ...
28
votes
3answers
1k views
Given a weighted dag, is there an O(V+E) algorithm to replace each weight with the sum of its ancestor weights?
The problem, of course, is double counting. It's easy enough to do for certain classes of DAGs = a tree, or even a serial-parallel tree. The only algorithm I have found which works on general DAGs in ...
