| Autor: |
Schmidt, Jonas, Schwentick, Thomas, Vortmeier, Nils, Zeume, Thomas, Kokkinis, Ioannis |
| Rok vydání: |
2019 |
| Předmět: |
|
| Druh dokumentu: |
Working Paper |
| Popis: |
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 formulas are from first-order logic, giving rise to the dynamic complexity class DynFO. This paper investigates extensions of DynFO in the spirit of parameterised algorithms. In this setting structures come with a parameter $k$ and the extensions allow additional "space" of size $f(k)$ (in the form of an additional structure of this size) or additional time $f(k)$ (in the form of iterations of formulas) or both. The resulting classes are compared with their non-dynamic counterparts and other classes. The main part of the paper explores the applicability of methods for parameterised algorithms to this setting through case studies for various well-known parameterised problems. |
| Databáze: |
arXiv |
| Externí odkaz: |
|
