49 citations · 106 across the 25 of their papers we have counts for
3 papers · 1 filter
Dynamic Complexity Meets Parameterised Algorithms
Jonas Schmidt, Thomas Schwentick, Nils Vortmeier +2
Dynamic Complexity studies the maintainability of queries with logical formulas in a setting where the underlying structure or database changes over time. Most often, these formula…
Dynamic Complexity of Parity Exists Queries
Nils Vortmeier, Thomas Zeume
Given a graph whose nodes may be coloured red, the parity of the number of red nodes can easily be maintained with first-order update rules in the dynamic complexity framework DynF…
A More General Theory of Static Approximations for Conjunctive Queries
Pablo Barceló, Miguel Romero, Thomas Zeume
Conjunctive query (CQ) evaluation is NP-complete, but becomes tractable for fragments of bounded hypertreewidth. Approximating a hard CQ by a query from such a fragment can thus al…