# Tagged Questions

84 views

### Decremental reachability in a grid graph

Consider an $n$ by $n$ grid graph. For example, the following. You can of course reach the top left corner from the bottom right. Now consider the graph dynamically with an arbitrary number of ...
89 views

### Dynamic distance from source in a directed graph (only incremental or only decremental)

At the beginning we have a directed unweighted graph of $n \leq 10^3$ vertices, and $m \leq 10^5$ edges, with some vertex being a source, and we perform updates and queries on it. An update is adding ...
125 views

### Finding shortest path from a node to any node of a particular type [closed]

I have an un-directed, un-weighted graph G.Starting from a given node A, i want to find whether there is a path from A to a node of a certain type .There can be many nodes of that type. The problem is ...
36 views

### Order of steps in Kosaraju-Sharir

The Wikipedia summary of the Kosaraju-Sharir algorithm is as follows: Let G be a directed graph and S be an empty stack. While S does not contain all vertices. Choose an arbitrary ...
90 views

### directed graph data structure with fast in/out neighbor query

If I store a directed graph $G$ in adjacency list format, one can find all the out-neighbors $j$ of a given vertex $i$ in $\mathcal O(d)$ time, where $d$ is the max degree of the graph. These are all ...
144 views

### Compact representation of paths in a graph

I've a subset of the simple paths in a graph. The length of the paths is bounded by $d$. What's the most compact way (memory-wise) I can represent the paths such that no other paths apart from the ...
212 views

### Data structure for finding the sum of edge weights on a path

Let $T$ be a tree, and there is a weight function on the edges $w:E\to X$. $(X,\oplus)$ is a monoid structure. Define $f(u,v) = \bigoplus_{i=1}^k w(e_i)$, where $e_1,\ldots,e_k$ is the unique path ...
169 views

### An incrementally-condensed transitive-reduction of a DAG, with efficient reachability queries

Is there an incremental directed graph data structure that has the following properties: Keeps an internal graph structure as a DAG, and the graph is accessible (notwithstanding other helper ...
936 views

### Maintaining an efficient ordering where you can insert elements “in between” any two other elements in the ordering?

Imagine I have an ordering on a bunch of elements like so: Where an arrow $X \leftarrow Y$ means $X < Y$. It is also transitive: \$\left(X < Y\right) \wedge \left(Y < Z\right) \implies ...
310 views

### Are link-cut trees ever used in practice, for max flow computation or other applications?

Many max flow algorithms that I commonly see implemented, Dinic's algorithm, push relabel, and others, can have their asymptotic time cost improved through the use of dynamic trees (also known as ...
160 views

### Is it possible to use plants as a medium to store data? By what data structure?

my question is simple. Is it possible to use plants as a medium to store data? My opinion is: Possible, but we need to solve, how to distinguish 2 states. Duplication and CRC of stored DATA is quiet ...
1k views

### Retrieving the shortest path of a dynamic graph

I'm studying shortest paths in directed graphs currently. There are many efficient algorithms for finding the shortest path in a network, like dijkstra's or bellman-ford's. But what if the graph is ...
610 views

### Practical applications of disjoint set datastructure

I know that the disjoint set datastructure is used to keep track of the connected components of an undirected graph when the edges are added to the graph dynamically . I also know that is is used in ...