The Exponential Time complexity of counting (quantum) graph homomorphisms

DOI10.1007/978-3-030-30786-8_28MaRDI QIDQ2301557zbMATH OpenOpenAlexFDO

Authors Hubie Chen, Radu Curticapean, Holger Dell

Publication date 24 February 2020

Full work available at URL https://doi.org/10.1007/978-3-030-30786-8_28

zbMATH Keywords

complexity dichotomycounting complexityExponential Time Hypothesisgraph homomorphismssurjective homomorphisms

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1545676
• scientific article; zbMATH DE number 1445311
• Quantum time complexity and algorithms for pattern matching on labeled graphs
• Exponential-time quantum algorithms for graph coloring problems
• Exponential-time quantum algorithms for graph coloring problems
• Quantum Query Complexity of Some Graph Problems
• Automata, Languages and Programming
• Quantum query complexity of subgraph isomorphism and homomorphism
• SOFSEM 2004: Theory and Practice of Computer Science
• scientific article; zbMATH DE number 6943289

Cited in

(6)

• Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2
• Quantum time complexity and algorithms for pattern matching on labeled graphs
• New plain-exponential time classes for graph homomorphism
• Algebraic global gadgetry for surjective constraint satisfaction
• Exponential time complexity of the complex weighted Boolean \#CSP
• On counting (quantum-)graph homomorphisms in finite fields of prime order

This page was built for publication: The Exponential Time complexity of counting (quantum) graph homomorphisms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2301557)