The dynamic complexity of acyclic hypergraph homomorphisms

DOI10.1007/978-3-030-86838-3_18OpenAlexW3204154240MaRDI QIDQ2672439

Nils Vortmeier, Ioannis Kokkinis

Publication date: 8 June 2022

Full work available at URL: https://arxiv.org/abs/2107.06121

zbMATH Keywords

conjunctive queriesdynamic complexityhypergraph homomorphisms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The dynamic complexity of acyclic hypergraph homomorphisms