# Questions tagged [dynamic-algorithms]

The tag has no usage guidance.

27 questions
Filter by
Sorted by
Tagged with
62 views

### Updating (minimal) DFA incrementally

Is there algorithm to incrementally update (minimal) DFA? Namely, having relatively large minimized DFA I want to update it incrementally using union and sudtraction with other (relatively small, ...
• 421
87 views

### Dynamic connectivity with known history, for maximal connected component span

Consider a graph in which edges are added and removed over time. Define the span of a connected component as the product of its number of vertices and the longest duration for which it remains a ...
324 views

### Dynamic transitive closure with immediate new reachability facts

The typical definition of dynamic transitive closure (or reachability) uses two types of queries: the first one is an update (edge deletion/insertion) and the second one is a reachability query. Thus, ...
• 421
147 views

### Dynamic matrix-matrix multiplication

Suppose A and B are initial Boolean matrices. Let C = A*B. Suppose one can perform the sequence of the next operations: "set A[i,j] = 1", "set B[i,j] = 1". The result of each ...
• 421
1 vote
157 views

### What are some techniques for "balancing" a tree beside heavy-light and centroid decomposition?

The only techniques i know are those in the title.
• 195
180 views

### Maintaining the value of a polynomial over a dynamically updated input

Let $P(x_1, x_2, \ldots, x_n)$ be a polynomial over a fixed finite field. Suppose we are given the value of $P$ on some vector $y \in \{0,1\}^n$ and the vector $y$. We now want to compute the value ...
1 vote
119 views

### Algorithm for maximum bipartite matching with arriving edges?

Given a bipartite graph with fixed nodes and incrementally arriving edges, is there any efficient algorithm to compute and update the maximum matching?
147 views

### Set query in a universe with overlapping sets

Suppose we have a universe $U$ of $n$ items $u_1,u_2,u_3,...,u_n$. And a collection of sets (no restriction on being disjoint or exhaustive etc.) which cover some items. Size of each set is bounded by ...
• 171
920 views

### Can differential equations be classed into their own complexity classes?

Problems have been, as a whole, classified, thanks to Computational Complexity. But, in differential equations, is it possible to classify differential equations depending on their computational ...
• 101
55 views

### 2-dimensional dynamic set retrieval

For the following, $(w,x) >= (y,z)$ iff $w >= y$ and $x >= z$. I have a list, $L$, of $k$ points with integer coordinates ranging from $0$ to $n-1$. Each point has an associated set. I ...
• 1,099
108 views

### Online bridge and nonbridge counting (identification)

I was wondering if there is any efficient (possibly armortized poly-logarithmic) online algorithm which supports counting (identification) of bridges- and non-bridges online, i.e. during a sequence of ...
1 vote
825 views

### dynamic algorithms for the subset-sum problem hold for vectors?

I have a vector (er, array) that is the sum of a number of other known vectors. I would like to reverse the process and find the specific known vectors that were summed to make the final vector. The ...
• 111
2k views

### What is the fastest deterministic algorithm for incremental DAG reachability?

As the title. The incremental algorithm maintains the reachability information of a DAG when it undergoes a series of edge insertions (but no deletions). And the algorithm supports constant query (if ...
• 519
1 vote
187 views

### Relation between static Nash equlibria and dynamic equlibria

I am working on Normal form continuous games. I am not very familiar with dynamic game theory. I would like to know if there is any relation between static Nash equilibria and dynamic equilibria. If ...
• 21
387 views

### Optimal insertion times in insertion-only data structures beyond Bentley-Saxe

The Bentley-Saxe trick allows us to go from a static decomposable problem to a problem admitting insertions, where the insertion time is off the optimal time by a factor of $\log n$. Is this tight ? ...
345 views

### What is the fastest deterministic algorithm for incremental dynamic tree reachability?

As the title. The dynamic algorithm maintains the transitive closure of a tree when the tree undergoes a series of edge insertions (but no deletions)? And the algorithm supports constant query time. ...
• 519
2k views

### Dynamic Data structure for All nearest smaller values

I need a data structure that stores a sequence of numbers and supports the following operations. The input to each operation includes the position of an item in the current sequence (not the value or ...
• 137
873 views

### What is the fastest deterministic algorithm for dynamic digraph reachability with no edge deletion?

What is the best deterministic result for maintaining the dynamic transitive closure in a directed graph with only edge insertion? I read some papers on the dynamic transitive closure problem with ...
• 519
6k views

### Space complexity to compute the optimal string alignment for the Levenshtein edit distance

If we are given two strings of size $n_1$ and $n_2$, the standard Levenshtein edit distance computation is by a dynamic algorithm with time complexity $O(n_1 n_2)$ and space complexity $O(n_1 n_2)$. (...
• 8,896
1k views

### Determining connectivity for a fully dynamic graph with vertex/subgraph insertion and deletion

I am looking for a solution to the following problem and wonder if anyone could point me to some existing research on this topic. I am coming from a real world application of graph so bear with me if ...
1 vote
194 views

### Dynamic k-shortest paths in a weighted transducer

I'm looking for references relating to dynamically computing the k-shortest output paths through a stochastic, acyclic, weighted transducer that is being constructed on-the-fly. In this scenario ...
• 433
1 vote
611 views

### Remove specific edge from ST (link-cut) tree

ST (or link cut) trees are a special kind of trees used for dynamic graph algorithms. They support the following operations in logarithmic time: CUT(v) Deletes the edge from v to its parent JOIN(v, w)...
• 13
374 views

### Applications of an access lemma for dynamic forests?

Sleator and Tarjan's amortized analysis of splay trees builds on their so-called Access Lemma. For purposes of analysis, assign an arbitrary weight to each node $v$, and let $size(v)$ denote the sum ...
• 23.1k
530 views

### Searching nodes in semi-splay tree

If you search for a node in a semi-splay tree, it's basically to push certain nodes closer to the root, to reduce future search operations. My course also says that if you search for a node and the ...
• 227
836 views

### What is the initialization time of a link-cut tree?

Link-cut tree is a data structure invented by Sleator and Tarjan, which supports various operations and queries on a $n$-node forest in time $O(\log n)$. (For example, operation link combines two ...
• 7,638