scientific article; zbMATH DE number 7378366

DOI10.4230/LIPIcs.MFCS.2018.49zbMath1495.68174arXiv1802.06103MaRDI QIDQ5005151

Andreas Göbel, J. A. Gregor Lagodzinski, Karen Seidel

Publication date: 4 August 2021

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

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

algorithmsgraph homomorphismstheorycomplexity dichotomycounting modulo a prime

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Enumeration in graph theory (05C30) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (2)

Unnamed Item ⋮ Counting Homomorphisms to $K_4$-Minor-Free Graphs, Modulo 2

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Holographic algorithms: from art to science
• On the construction of parallel computers from various basis of Boolean functions
• On the complexity of H-coloring
• The complexity of partition functions
• The complexity of counting homomorphisms to cactus graphs modulo 2
• The complexity of parity graph homomorphism: an initial investigation
• On Counting Independent Sets in Sparse Graphs
• PP is as Hard as the Polynomial-Time Hierarchy
• Counting Homomorphisms to Square-Free Graphs, Modulo 2
• On the Structure of Polynomial Time Reducibility
• A Complexity Dichotomy for Partition Functions with Mixed Signs
• Graph Homomorphisms with Complex Values: A Dichotomy Theorem

This page was built for publication: