Colouring, constraint satisfaction, and complexity
From MaRDI portal
Publication:458466
DOI10.1016/j.cosrev.2008.10.003zbMath1302.68251OpenAlexW2199961663WikidataQ56389140 ScholiaQ56389140MaRDI QIDQ458466
Publication date: 7 October 2014
Published in: Computer Science Review (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.cosrev.2008.10.003
Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Coloring of graphs and hypergraphs (05C15) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20)
Related Items
Constraint satisfaction and semilinear expansions of addition over the rationals and the reals ⋮ Tractability in constraint satisfaction problems: a survey ⋮ In praise of homomorphisms ⋮ A Galois Connection for Valued Constraint Languages of Infinite Size ⋮ Binary constraint satisfaction problems defined by excluded topological minors ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ A tetrachotomy of ontology-mediated queries with a covering axiom ⋮ On planar valued CSPs ⋮ A complexity dichotomy for signed \(\mathbf{H}\)-colouring ⋮ Obstructions to partitions of chordal graphs ⋮ A new line of attack on the dichotomy conjecture ⋮ Homogeneous 1‐based structures and interpretability in random structures ⋮ Using a Min-Cut generalisation to go beyond Boolean surjective VCSPs ⋮ Hybrid Tractable Classes of Constraint Problems ⋮ The Complexity of Valued CSPs ⋮ Backdoor Sets for CSP. ⋮ ON CONSTRAINTS AND DIVIDING IN TERNARY HOMOGENEOUS STRUCTURES ⋮ Reflexive graphs with near unanimity but no semilattice polymorphisms ⋮ The \(C_{k}\)-extended graft construction ⋮ Unnamed Item ⋮ Binary simple homogeneous structures are supersimple with finite rank ⋮ Graph partitions with prescribed patterns ⋮ Connected obstructions to full graph homomorphisms ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs ⋮ Dualities in full homomorphisms ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Unnamed Item
Cites Work
- Locally constrained graph homomorphisms -- structure, complexity, and applications
- Absolute reflexive retracts and absolute bipartite retracts
- On the complexity of colouring by superdigraphs of bipartite graphs
- The core of a graph
- \(H\)-coloring dichotomy revisited
- List matrix partitions of chordal graphs
- The strong perfect graph theorem
- Digraph matrix partitions and trigraph homomorphisms
- List homomorphisms of graphs with bounded degrees
- The effect of two cycles on the complexity of colourings by directed graphs
- A combinatorial algorithm for MAX CSP
- Decomposition by clique separators
- A retraction problem in graph theory
- A graph coloring algorithm for large scale scheduling problems
- On the complexity of H-coloring
- Star-cutsets and perfect graphs
- Chromatically optimal rigid graphs
- List homomorphisms to reflexive graphs
- Polynomial graph-colorings
- Efficient characterizations of \(n\)-chromatic absolute retracts
- Precoloring extension. I: Interval graphs
- On classes of relations and graphs determined by subobjects and factorobjects
- A linear-time algorithm for testing the truth of certain quantified Boolean formulas
- On colorings of graphs without short cycles
- On the algebraic structure of combinatorial problems
- Characterising tractable constraints
- Grötzsch's 3-color theorem and its counterparts for the torus and the projective plane
- On sparse graphs with given colorings and homomorphisms.
- The complexity of \(H\)-colouring of bounded degree graphs
- Conjunctive-query containment and constraint satisfaction
- Graph products, Fourier analysis and spectral techniques
- A new tractable class of constraint satisfaction problems
- Absolute retracts of bipartite graphs
- Partitioning chordal graphs into independent sets and cliques
- Hereditarily hard \(H\)-colouring problems
- Networks of constraints: Fundamental properties and applications to picture processing
- Duality theorems for finite structures (characterising gaps and good characterisations)
- A Fourier-theoretic perspective on the Condorcet paradox and Arrow's theorem.
- Dichotomies for classes of homomorphism problems involving unary functions
- Complexity of tree homomorphisms
- Aspects of structural combinatorics. (Graph homomorphisms and their use)
- List homomorphisms and circular arc graphs
- Grad and classes with bounded expansion. I: Decompositions
- Grad and classes with bounded expansion. II: Algorithmic aspects
- Independent sets in graph powers are almost contained in juntas
- On digraph coloring problems and treewidth duality
- Generalised dualities and maximal finite antichains in the homomorphism order of relational structures
- A dichotomy for minimum cost graph homomorphisms
- Forbidden lifts (NP and CSP for combinatorialists)
- Grad and classes with bounded expansion. III: Restricted graph homomorphism dualities
- Matrix partitions of perfect graphs
- A dualistic approach to bounding the chromatic number of a graph
- On realizations of point determining graphs, and obstructions to full homomorphisms
- Retractions onto series-parallel posets
- Minimum cost and list homomorphisms to semicomplete digraphs
- Tree-depth, subgraph coloring and homomorphism bounds
- Folding
- Closed systems of functions and predicates
- Absolute planar retracts and the four colour conjecture
- Cuts and bounds
- Finite posets and topological spaces in locally finite varieties
- Complexity Classifications of Boolean Constraint Satisfaction Problems
- Classification of Homomorphisms to Oriented Cycles and of k-Partite Satisfiability
- Linear time low tree-width partitions and algorithmic consequences
- Many Facets of Dualities
- A polynomial-time algorithm for near-unanimity graphs
- Absolute Retracts and Varieties of Reflexive Graphs
- Projectivity and independent sets in powers of graphs
- Proof verification and the hardness of approximation problems
- Note on projective graphs
- Near-Unanimity Functions and Varieties of Reflexive Graphs
- Reflection positivity, rank connectivity, and homomorphism of graphs
- On Dinur’s proof of the PCP theorem
- First-order Definable Retraction Problems for Posets and Reflexive Graphs
- A Dichotomy Theorem on Fixed Points of Several Nonexpansive Mappings
- Classification of Bipartite Boolean Constraint Satisfaction through Delta-Matroid Intersection
- Expander graphs and their applications
- Combinatorial Proof that Subprojective Constraint Satisfaction Problems are NP-Complete
- Varieties with few subalgebras of powers
- Structural Properties of Sparse Graphs
- Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction
- The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
- Linear-time algorithms for testing the satisfiability of propositional horn formulae
- Interval digraphs: An analogue of interval graphs
- The Complexity of Colouring by Semicomplete Digraphs
- A graph formulation of a school scheduling algorithm
- Applications of product colouring
- On the Structure of Polynomial Time Reducibility
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Closure properties of constraints
- List Partitions
- The Complexity of the Extendibility Problem for Finite Posets
- Acyclic Homomorphisms and Circular Colorings of Digraphs
- Computational Complexity of Compaction to Reflexive Cycles
- Bi‐arc graphs and the complexity of list homomorphisms
- The Ramsey number R(3, t) has order of magnitude t2/log t
- Precoloring Extension III: Classes of Perfect Graphs
- Duality and Polynomial Testing of Tree Homomorphisms
- A new line of attack on the dichotomy conjecture
- Generalized Majority-Minority Operations are Tractable
- Classifying the Complexity of Constraints Using Finite Algebras
- Tractability and Learnability Arising from Algebras with Few Subpowers
- The complexity of satisfiability problems
- Mathematical Foundations of Computer Science 2003
- A Characterisation of First-Order Constraint Satisfaction Problems
- Minimum Cost Homomorphisms to Reflexive Digraphs
- A Simple Algorithm for Mal'tsev Constraints
- Full Constraint Satisfaction Problems
- Short Answers to Exponentially Long Questions: Extremal Aspects of Homomorphism Duality
- Dualities for Constraint Satisfaction Problems
- Minimum Cost Homomorphism Dichotomy for Locally In-Semicomplete Digraphs
- Nombre chromatique et plus longs chemins d'un graphe
- Zur algebraischen Begründung der Graphentheorie. I
- On sentences which are true of direct unions of algebras
- The PCP theorem by gap amplification
- Products of absolute retracts
- The NP-completeness column: An ongoing guide
- Colorings and homomorphisms of degenerate and bounded degree graphs
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
