The dynamic-algorithms tag has no wiki summary.
3
votes
1answer
100 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 ? ...
3
votes
1answer
114 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.
...
4
votes
1answer
211 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 ...
11
votes
1answer
162 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 ...
5
votes
2answers
213 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)$. ...
7
votes
2answers
210 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
0answers
131 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 ...
1
vote
1answer
211 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, ...
11
votes
0answers
180 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 ...
5
votes
1answer
230 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 ...
6
votes
2answers
434 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 ...
0
votes
2answers
588 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) ...
22
votes
2answers
484 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 ...
