Questions tagged [dynamic-algorithms]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
6 votes
0 answers
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, ...
gsv's user avatar
  • 421
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 ...
Matthieu Latapy's user avatar
3 votes
1 answer
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, ...
gsv's user avatar
  • 421
4 votes
0 answers
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 ...
gsv's user avatar
  • 421
1 vote
1 answer
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.
GEP's user avatar
  • 195
10 votes
2 answers
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 ...
Tatiana Starikovskaya's user avatar
1 vote
0 answers
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?
Chuancong Gao's user avatar
2 votes
1 answer
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 ...
sbzk's user avatar
  • 171
10 votes
1 answer
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 ...
sonamtex's user avatar
  • 101
2 votes
0 answers
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 ...
bbejot's user avatar
  • 1,099
3 votes
0 answers
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 ...
antarcticfox's user avatar
1 vote
0 answers
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 ...
Brannon's user avatar
  • 111
16 votes
0 answers
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 ...
wei wang's user avatar
  • 519
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 ...
Vinay's user avatar
  • 21
3 votes
1 answer
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 ? ...
Suresh Venkat's user avatar
4 votes
1 answer
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. ...
wei wang's user avatar
  • 519
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 ...
Vk1's user avatar
  • 137
18 votes
1 answer
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 ...
wei wang's user avatar
  • 519
12 votes
2 answers
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)$. (...
a3nm's user avatar
  • 8,896
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 ...
Thuan Seah Tan's user avatar
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 ...
s8soj3o289's user avatar
1 vote
1 answer
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)...
dancsi's user avatar
  • 13
13 votes
0 answers
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 ...
Jeffε's user avatar
  • 23.1k
6 votes
1 answer
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 ...
Aerus's user avatar
  • 227
8 votes
2 answers
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 ...
Hsien-Chih Chang 張顯之's user avatar
-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) ...
ntsue's user avatar
  • 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 ...
Suresh Venkat's user avatar