One hierarchy spawns another

DOI10.1145/2603088.2603107zbMath1394.68172arXiv1307.1353OpenAlexW2078803743MaRDI QIDQ4635616

Moritz Müller, Hubie Chen

Publication date: 23 April 2018

Published in: Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) (Search for Journal in Brave)

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

zbMATH Keywords

homomorphismsparameterized complexityconjunctive queriesgraph decompositions

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Database theory (68P15) Specification and verification (program logics, model checking, etc.) (68Q60) Structural characterization of families of graphs (05C75) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (3)

On the $AC^0$ Complexity of Subgraph Isomorphism ⋮ Decomposing Quantified Conjunctive (or Disjunctive) Formulas ⋮ How many variables are needed to express an existential positive query?

This page was built for publication: One hierarchy spawns another