The dynamic complexity of acyclic hypergraph homomorphisms
From MaRDI portal
Publication:2672439
DOI10.1007/978-3-030-86838-3_18MaRDI QIDQ2672439
Nils Vortmeier, Ioannis Kokkinis
Publication date: 8 June 2022
Full work available at URL: https://arxiv.org/abs/2107.06121
68R10: Graph theory (including graph drawing) in computer science
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Elements of finite model theory.
- On the complexity of H-coloring
- Properties that characterize LOGCFL
- Dyn-FO: A parallel, dynamic complexity class
- Nonrecursive incremental evaluation of Datalog queries
- The dynamic descriptive complexity of \(k\)-clique
- The dynamic complexity of formal languages
- On the Desirability of Acyclic Database Schemes
- Degrees of acyclicity for hypergraphs and relational database schemes
- Dynamic Complexity under Definable Changes
- The complexity of acyclic conjunctive queries
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- Power of Natural Semijoins
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Reachability Is in DynFO
- Dynamic algorithms for graphs with treewidth 2