Enumerating homomorphisms

DOI10.1016/j.jcss.2011.09.006zbMath1253.68165OpenAlexW2914039150MaRDI QIDQ414933

Martin Grohe, Andrei A. Bulatov, Dániel Marx, Victor Dalmau

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.09.006

zbMATH Keywords

computational complexityenumerationhomomorphismsconstraint satisfaction

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Enumeration in graph theory (05C30)

Related Items (10)

Structural tractability of counting of solutions to conjunctive queries ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Semantic Acyclicity on Graph Databases ⋮ Generating clause sequences of a CNF formula ⋮ Dismantlability, connectedness, and mixing in relational structures ⋮ Finding a given number of solutions to a system of fuzzy constraints ⋮ Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms ⋮ Dismantlability, Connectedness, and Mixing in Relational Structures ⋮ Structural tractability of enumerating CSP solutions ⋮ The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side

Cites Work

• Unnamed Item
• Unnamed Item
• The core of a graph
• Towards a dichotomy theorem for the counting constraint satisfaction problem
• Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
• On the parameterized complexity of multiple-interval graph problems
• On the complexity of H-coloring
• On generating all maximal independent sets
• Structural tractability of enumerating CSP solutions
• The complexity of partition functions
• Size Bounds and Query Plans for Relational Joins
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Towards Sharp Inapproximability for Any 2-CSP
• The Complexity of the Counting Constraint Satisfaction Problem
• A dichotomy theorem for constraint satisfaction problems on a 3-element set
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• On counting homomorphisms to directed acyclic graphs
• The complexity of temporal constraint satisfaction problems
• Enumerating All Solutions for Constraint Satisfaction Problems
• The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
• Efficient Planarity Testing
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Classifying the Complexity of Constraints Using Finite Algebras
• The Approximability of Three-valued MAX CSP
• Uniform Constraint Satisfaction Problems and Database Theory

This page was built for publication: Enumerating homomorphisms