Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
type: Item
instance of: scholarly article
title: Maximum \(H\)-colourable subdigraphs and constraint optimization with arbitrary weights
zbMATH Open document ID: 1115.68143
author: Peter Jonsson
author: Andrei Krokhin
published in: Journal of Computer and System Sciences
publication date: 2007-05-30T00:00:00Z
Mathematics Subject Classification ID: 68T20
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 5159570
zbMATH Keywords: maximum constraint satisfaction problem
zbMATH Keywords: digraph \(H\)-colouring
zbMATH Keywords: complexity
zbMATH Keywords: dichotomy
MaRDI profile type: Publication
full work available at URL: j.jcss.2007.02.001
OpenAlex ID: W2142884756
cites work: Q4258216
cites work: An Application of Combinatorial Optimization to Statistical Physics and Circuit Layout Design
cites work: Semiring-based CSPs and valued CSPs: Frameworks, properties, and comparison
cites work: A dichotomy theorem for constraint satisfaction problems on a 3-element set
cites work: Algorithmic Learning Theory
cites work: The complexity of soft constraint satisfaction
cites work: Supermodular functions and the complexity of MAX CSP
cites work: A dichotomy theorem for maximum generalized satisfiability problems.
cites work: Complexity classifications of Boolean constraint satisfaction problems
cites work: Q4737176
cites work: Learnability of quantified formulas.
cites work: The complexity of counting homomorphisms seen from the other side
cites work: Q4530231
cites work: The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Hypertree decompositions and tractable queries
cites work: On bounded occurrence constraint satisfaction
cites work: Some optimal inapproximability results
cites work: On the complexity of H-coloring
cites work: Q4828516
cites work: Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights
cites work: The Approximability of Three-valued MAX CSP
cites work: The approximability of constraint satisfaction problems
cites work: Conjunctive-query containment and constraint satisfaction
cites work: Maximum Constraint Satisfaction on Diamonds
cites work: Numerical Optimization
cites work: The complexity of satisfiability problems
DOI: 10.1016/J.JCSS.2007.02.001
description: scientific article; zbMATH DE number 5159570