Complexity models for incremental computation

DOI10.1016/0304-3975(94)90159-7zbMath0808.68061OpenAlexW2078423836MaRDI QIDQ1331947

Jeffrey Scott Vitter, Roberto Tamassia, Peter Bro Miltersen, Sairam Subramanian

Publication date: 29 August 1994

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(94)90159-7

zbMATH Keywords

complexityincremental computation

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (19)

On dynamic bit-probe complexity ⋮ Lower bounds for dynamic transitive closure, planar point location, and parentheses matching ⋮ A survey on combinatorial optimization in dynamic environments ⋮ Dynamic trees as search trees via Euler tours, applied to the network simplex algorithm ⋮ Dyn-FO: A parallel, dynamic complexity class ⋮ Incremental algorithm for maintaining a DFS tree for undirected graphs ⋮ On Dynamic DFS Tree in Directed Graphs ⋮ Fully Dynamic Transitive Closure in plane dags with one source and one sink ⋮ Listing the bonds of a graph in \(\widetilde{O} (n)\)-delay ⋮ Incremental recomputation in local languages. ⋮ Dynamic Complexity of the Dyck Reachability ⋮ Work-sensitive dynamic complexity of formal languages ⋮ On the cell probe complexity of polynomial evaluation ⋮ Incremental problems in the parameterized complexity setting ⋮ Unnamed Item ⋮ A fully dynamic algorithm for maintaining the transitive closure ⋮ Arity bounds in first-order incremental evaluation and definition of polynomial time database queries ⋮ Dynamic DFS in Undirected Graphs: Breaking the $O(m)$ Barrier ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The design of dynamic data structures
• Proving relative lower bounds for incremental algorithms
• A topological approach to dynamic graph connectivity
• Optimal dynamization of decomposable searching problems
• A data structure for dynamic trees
• A complexity theory based on Boolean algebra
• Problems complete for deterministic logarithmic space
• The Complexity of Maintaining an Array and Computing Its Partial Sums
• A New Approach to Stable Matching Problems

This page was built for publication: Complexity models for incremental computation