15

There is no need for the tradeoff that Yuval suggests. The entire optimal editing sequence can be computed in $O(nm)$ time and $O(n+m)$ space, using a mixture of dynamic programming and divide-and-conquer first described by Dan Hirschberg. (A linear space algorithm for computing maximal common subsequences. Commun. ACM 18(6):341–343, 1975.) Intuitively, ...


10

An old paper by Italiano (G.F. Italiano. Amortized efficiency of a path retrieval data structure. Theoretical Computer Science, 48(2–3):273–281, 1986.) gives a data structure that supports edge insertions in $O(n)$ amortized time and reachability queries in constant time. I'm not aware of better incremental algorithms.


7

If you modify a balanced binary search tree (whose inorder traversal is the sequence order) so that each node stores the minimum value of its descendants (and if you know the path to x) then you can easily find the nearest smaller value: it must either be on the path to x, or in a left subtree descending from the path. In the first case, you have a ...


7

Your idea generalizes as follows: given an algebraic circuit (over the finite field) or Boolean circuit (computing the bit-wise representation of your finite field elements) computing $P$, then maintain the value at each gate in the circuit. When you change the $i$-th bit of $y$, simply propagate that change along the DAG of the circuit, starting from the ...


5

One can reverse the roles of elements and sets. This can be seen by considering a Boolean matrix of size $m\times n$ where there are $m$ sets and $n$ is the size of the universe. The $i$th row corresponds to the characteristic vector of the $i$th set. Transposing this matrix reverses the roles of sets and elements ($n$ sets and $m$ elements). Now the ...


5

A first observation in the direction of decidability of ODEs is this paper by Avigad, Clarke and Gao, which classifies the complexity of $\delta$-decidability, in which solutions are to be found within a certain bounded error (the "delta") in one direction. one of the main results is that $\delta$-solvability of (Lipschitz-continuous) ODEs is $\mathrm{...


5

It's easy to modify your monomial-storing approach so that each update takes time only proportional to the number of changed monomials: just update the total polynomial value by adding the new value and subtracting the old value for each changed monomial. If you have a read-once formula for $P$ (i.e. every variable appears at a single leaf of the formula ...


4

The best I can find for this is $O(\log n)$ amortized update time with constant query time. The basic idea is that if you know both preorder and postorder for a tree, you can recover reachability: there is a path from $x$ to $y$ iff $x$ is before $y$ in preorder and after it in postorder. There are several data structures that can maintain a list of items, ...


4

This isn't a trivial question at all. One of the problems you'll have finding algorithms for this is the disconnectedness (pun intended) of the work on dynamic graphs. Thorup et al.'s work (the one you mention) is probably the best start for the kind of thing you're looking for. You could also try Bhadra & Ferreira, they're probably getting a bit off-...


3

Think about your question in reverse: suppose you have a dynamic data structure for some problem — does that imply that you can solve it statically, faster by a log? Why should it? And in fact it is not true. Consider range counting in one-dimensional intervals, in a comparison model of computation. That is, the data is a set $S$ of numbers, the query is an ...


3

The algorithm you describe that runs in space $O(n_1 + n_2)$ actually recovers the final edit, and the state just before the final edit. So if you run this algorithm $O(n_1 + n_2)$ times, you can recover the entire edit sequence, at the expense of increasing the runtime. In general, there is a time-space trade-off which is controlled by the number of rows ...


2

The paper "Algorithmic Meta Theorems for Circuit Classes of Constant and Logarithmic Depth" (Elberfeld, Jacobi, Tantau) gives a nice balanced tree decomposition based on tree contraction in $TC^0$: https://eccc.weizmann.ac.il/report/2011/128/ Another nice $TC^0$-decomposition is based on so-called TSLPs in the paper "A Universal Tree Balancing Theorem" (...


1

The Vertex updates can be handled using edge updates as follows (Although a bit inefficient as it makes deg(u) calls to edge update function): AddVertex(G,u,Adj(u)):- /* Adj(u) is the vertices adjacent to u after adding u */ For each v in Adj(u) do AddEdge(G, (u,v)) DeleteVertex(G,u):- For each v in Adj(u) do DeleteEdge(G, (u,v)) ...


1

There is an $\tilde{O}(nK)$ time algorithm given by Chao Xu: Faster pseudo-polynomial time algorithms for PARTITION


Only top voted, non community-wiki answers of a minimum length are eligible