Enumerating homomorphisms

DOI10.1016/J.JCSS.2011.09.006zbMATH Open1253.68165OpenAlexW2914039150MaRDI QIDQ414933FDOQ414933

Martin Grohe, Andrei A. Bulatov, Dániel Marx, Víctor 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

Recommendations

• Enumerating homomorphisms
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The complexity of the counting constraint satisfaction problem
• Structural tractability of enumerating CSP solutions
• Counting homomorphisms and partition functions

zbMATH Keywords

computational complexityenumerationconstraint satisfactionhomomorphisms

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (12)

• Generating clause sequences of a CNF formula
• Dismantlability, Connectedness, and Mixing in Relational Structures
• Dismantlability, connectedness, and mixing in relational structures
• Title not available (Why is that?)
• Structural tractability of counting of solutions to conjunctive queries
• Finding a given number of solutions to a system of fuzzy constraints
• The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
• Structural tractability of enumerating CSP solutions
• Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms
• ENUMERATION OF HOMOMORPHISMS AND SURFACE-COVERINGS
• The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side
• Semantic Acyclicity on Graph Databases

This page was built for publication: Enumerating homomorphisms

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