The complexity of surjective homomorphism problems-a survey
type: Item
instance of: scholarly article
title: The complexity of surjective homomorphism problems-a survey
zbMATH Open document ID: 1246.05104
author: Manuel Bodirsky
author: Jan Kára
author: Barnaby Martin
published in: Discrete Applied Mathematics
publication date: 2012-08-14T00:00:00Z
Mathematics Subject Classification ID: 05C60
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6065731
zbMATH Keywords: surjective homomorphisms
zbMATH Keywords: computational complexity
zbMATH Keywords: constraint satisfaction
MaRDI profile type: Publication
full work available at URL: j.dam.2012.03.029
OpenAlex ID: W1998601876
cites work: The Complexity of Colouring by Semicomplete Digraphs
cites work: The Complexity of Rooted Phylogeny Problems
cites work: A dichotomy theorem for constraint satisfaction problems on a 3-element set
cites work: Complexity of conservative constraint satisfaction problems
cites work: Classifying the Complexity of Constraints Using Finite Algebras
cites work: The complexity of global cardinality constraints
cites work: The Complexity of the List Partition Problem for Graphs
cites work: \(2K_{2}\) vertex-set partition into nonempty parts
cites work: On generating all solutions of generalized satisfiability problems
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Q5365146
cites work: FindingH-partitions efficiently
cites work: List homomorphisms to reflexive graphs
cites work: List homomorphisms and circular arc graphs
cites work: Bi‐arc graphs and the complexity of list homomorphisms
cites work: Retractions to Pseudoforests
cites work: List Partitions
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: A complete complexity classification of the role assignment problem
cites work: Covering graphs with few complete bipartite subgraphs
cites work: Computing Vertex-Surjective Homomorphisms to Partially Reflexive Trees
cites work: Q4828516
cites work: Parameterizing Cut Sets in a Graph by the Number of Their Components
cites work: On disconnected cuts and separators
cites work: On the algebraic structure of combinatorial problems
cites work: The Approximability of Three-valued MAX CSP
cites work: Coloring mixed hypertrees
cites work: On the Structure of Polynomial Time Reducibility
cites work: Q3221403
cites work: Finding Vertex-Surjective Graph Homomorphisms
cites work: Undirected connectivity in log-space
cites work: Tractable cases of the extended global cardinality constraint
cites work: The complexity of satisfiability problems
cites work: The external constraint 4 nonempty part sandwich problem
cites work: Computing role assignments of chordal graphs
cites work: Computational Complexity of Compaction to Reflexive Cycles
cites work: Compaction, Retraction, and Constraint Satisfaction
cites work: Computational complexity of compaction to irreflexive cycles
cites work: A complete and equal computational complexity classification of compaction and retraction to all graphs with at most four vertices and some general results
cites work: Algorithms for Partition of Some Class of Graphs under Compaction
DOI: 10.1016/J.DAM.2012.03.029
description: scientific article; zbMATH DE number 6065731