Questions tagged [dynamic-algorithms]
The dynamic-algorithms tag has no usage guidance.
26
questions
2
votes
0
answers
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 ...
- 693
3
votes
1
answer
257
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, ...
- 361
4
votes
0
answers
144
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 ...
- 361
1
vote
1
answer
154
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
10
votes
2
answers
173
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
0
answers
118
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?
- 111
2
votes
1
answer
146
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
10
votes
1
answer
869
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
2
votes
0
answers
54
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
3
votes
0
answers
106
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 ...
- 51
1
vote
0
answers
821
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
16
votes
0
answers
1k
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 ...
- 509
1
vote
0
answers
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
3
votes
1
answer
382
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 ? ...
- 31.9k
4
votes
1
answer
344
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.
...
- 509
4
votes
1
answer
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
17
votes
1
answer
828
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 ...
- 509
12
votes
2
answers
5k
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,224
8
votes
3
answers
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
0
answers
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
1
answer
598
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
13
votes
0
answers
366
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 ...
- 22.9k
6
votes
1
answer
526
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
8
votes
2
answers
829
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,618
-1
votes
4
answers
3k
views
Interesting variation to the subset sum problem
An interesting variation of the subset sum problem was presented to me by a friend from work:
Given a set S of positive integers, of size n, and integers a and K, is there a subset R (of the set S) ...
- 109
24
votes
2
answers
551
views
Parallel Dynamic Search
Is there a natural parallel analog to red-black trees with similar or even not-terribly-worse properties for updates while being reasonably work-efficient ?
More generally, what's the best we can do ...
- 31.9k