On the algebraic structure of combinatorial problems
From MaRDI portal
Publication:1276253
DOI10.1016/S0304-3975(97)00230-2zbMath0915.68074MaRDI QIDQ1276253
Publication date: 20 January 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
Related Items (99)
Constraint satisfaction and semilinear expansions of addition over the rationals and the reals ⋮ Tractability in constraint satisfaction problems: a survey ⋮ CLAP: A New Algorithm for Promise CSPs ⋮ In praise of homomorphisms ⋮ The Complexity of General-Valued CSPs ⋮ Hard constraint satisfaction problems have hard gaps at location 1 ⋮ The complexity of constraint satisfaction games and QCSP ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ Nonnegative Weighted #CSP: An Effective Complexity Dichotomy ⋮ Supermodular functions and the complexity of MAX CSP ⋮ Domain permutation reduction for constraint satisfaction problems ⋮ Strong partial clones and the time complexity of SAT problems ⋮ Digraph matrix partitions and trigraph homomorphisms ⋮ Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis ⋮ An Algebraic Characterization of Testable Boolean CSPs ⋮ Towards a dichotomy theorem for the counting constraint satisfaction problem ⋮ Circuit satisfiability and constraint satisfaction around Skolem arithmetic ⋮ Complexity Classifications for Logic-Based Argumentation ⋮ Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy ⋮ Ideal Membership Problem over 3-Element CSPs with Dual Discriminator Polymorphism ⋮ A strong Mal'cev condition for locally finite varieties omitting the unary type ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ List homomorphisms to separable signed graphs ⋮ Conservative constraint satisfaction re-revisited ⋮ A new line of attack on the dichotomy conjecture ⋮ Constraint satisfaction problem: what makes the problem easy ⋮ Maltsev digraphs have a majority polymorphism ⋮ Majority constraints have bounded pathwidth duality ⋮ Computing a partition function of a generalized pattern-based energy over a semiring ⋮ The Expressive Power of Valued Constraints: Hierarchies and Collapses ⋮ The complexity of surjective homomorphism problems-a survey ⋮ Hybrid tractability of valued constraint problems ⋮ Colouring, constraint satisfaction, and complexity ⋮ Unnamed Item ⋮ Weak bases of Boolean co-clones ⋮ Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint ⋮ Quantified Constraints in Twenty Seventeen ⋮ Bounded Tree-Width and CSP-Related Problems ⋮ Algebra and the Complexity of Digraph CSPs: a Survey ⋮ On Boolean primitive positive clones ⋮ Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms ⋮ The complexity of soft constraint satisfaction ⋮ Varieties with few subalgebras of powers ⋮ The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems ⋮ Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight ⋮ Constants and finite unary relations in qualitative constraint reasoning ⋮ Tractability conditions for numeric CSPs ⋮ Rigid binary relations on a 4-element domain ⋮ The expressive power of valued constraints: Hierarchies and collapses ⋮ Gap theorems for robust satisfiability: Boolean CSPs and beyond ⋮ Quantified constraint satisfaction and the polynomially generated powers property ⋮ On solvability of systems of polynomial equations ⋮ Recognizing frozen variables in constraint satisfaction problems ⋮ The complexity of counting homomorphisms seen from the other side ⋮ Unnamed Item ⋮ Combinatorial problems raised from 2-semilattices ⋮ A new tractable class of constraint satisfaction problems ⋮ Unnamed Item ⋮ Unnamed Item ⋮ The \(C_{k}\)-extended graft construction ⋮ A note on some collapse results of valued constraints ⋮ SDPs and robust satisfiability of promise CSP ⋮ Unnamed Item ⋮ A polynomial relational class of binary CSP ⋮ Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination ⋮ On the Computational Complexity of Monotone Constraint Satisfaction Problems ⋮ THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA ⋮ TERM EQUATION SATISFIABILITY OVER FINITE ALGEBRAS ⋮ Galois connections for patterns: an algebra of labelled graphs ⋮ \(H\)-coloring degree-bounded (acyclic) digraphs ⋮ Existentially restricted quantified constraint satisfaction ⋮ Universal algebra and hardness results for constraint satisfaction problems ⋮ Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems) ⋮ Minimization of locally defined submodular functions by optimal soft arc consistency ⋮ Relatively quantified constraint satisfaction ⋮ Unnamed Item ⋮ Approximability of the Maximum Solution Problem for Certain Families of Algebras ⋮ A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties ⋮ TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS ⋮ Unnamed Item ⋮ The number of clones determined by disjunctions of unary relations ⋮ A combinatorial constraint satisfaction problem dichotomy classification conjecture ⋮ Time Complexity of Constraint Satisfaction via Universal Algebra ⋮ Basics of Galois Connections ⋮ Recent Results on the Algebraic Approach to the CSP ⋮ Dualities for Constraint Satisfaction Problems ⋮ Partial Polymorphisms and Constraint Satisfaction Problems ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Conjunctive-query containment and constraint satisfaction ⋮ Unnamed Item ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ List homomorphism problems for signed trees ⋮ Commutative idempotent groupoids and the constraint satisfaction problem. ⋮ The expressive rate of constraints ⋮ Periodic constraint satisfaction problems: Tractable subclasses ⋮ \(H\)-coloring dichotomy revisited
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On the complexity of colouring by superdigraphs of bipartite graphs
- Fast parallel constraint satisfaction
- Characterising tractable constraints
- Networks of constraints: Fundamental properties and applications to picture processing
- Closed systems of functions and predicates
- On the parallel complexity of discrete relaxation in constraint satisfaction networks
- On binary constraint problems
- The complexity of satisfiability problems
This page was built for publication: On the algebraic structure of combinatorial problems
