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
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, 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
