On the algebraic structure of combinatorial problems
From MaRDI portal
Publication:1276253
DOI10.1016/S0304-3975(97)00230-2zbMATH Open0915.68074MaRDI QIDQ1276253FDOQ1276253
Authors: P. Jeavons 
Publication date: 20 January 1999
Published in: Theoretical Computer Science (Search for Journal in Brave)
Recommendations
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of satisfiability problems
- Characterising tractable constraints
- Title not available (Why is that?)
- Title not available (Why is that?)
- Closed systems of functions and predicates
- Title not available (Why is that?)
- Title not available (Why is that?)
- Networks of constraints: Fundamental properties and applications to picture processing
- On binary constraint problems
- On the parallel complexity of discrete relaxation in constraint satisfaction networks
- On the complexity of colouring by superdigraphs of bipartite graphs
- Fast parallel constraint satisfaction
Cited In (only showing first 100 items - show all)
- An algebraic characterization of testable Boolean CSPs
- In praise of homomorphisms
- Theory and Applications of Satisfiability Testing
- Tractability conditions for numeric CSPs
- The complexity of surjective homomorphism problems-a survey
- Recent Results on the Algebraic Approach to the CSP
- Weak bases of Boolean co-clones
- Quantified constraint satisfaction and the polynomially generated powers property
- Constraint satisfaction and semilinear expansions of addition over the rationals and the reals
- Tractability in constraint satisfaction problems: a survey
- Algebraic Combinatorics
- Title not available (Why is that?)
- The power of linear programming for general-valued CSPs
- Colouring, constraint satisfaction, and complexity
- TAYLOR TERMS, CONSTRAINT SATISFACTION AND THE COMPLEXITY OF POLYNOMIAL EQUATIONS OVER FINITE ALGEBRAS
- The exponential-time hypothesis and the relative complexity of optimization and logical reasoning problems
- Dualities for Constraint Satisfaction Problems
- Recognizing frozen variables in constraint satisfaction problems
- The expressive rate of constraints
- Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination
- Towards a dichotomy theorem for the counting constraint satisfaction problem
- Hybrid tractability of valued constraint problems
- The complexity of counting homomorphisms seen from the other side
- Title not available (Why is that?)
- Conservative constraint satisfaction re-revisited
- Complexity Classifications for Logic-Based Argumentation
- Relatively quantified constraint satisfaction
- Problems in algebraic combinatorics
- A polynomial relational class of binary CSP
- On uniform relationships between combinatorial problems
- List homomorphisms to separable signed graphs
- On linear combinatorics. I: Concurrency---an algebraic approach
- Nonnegative weighted \#CSP: an effective complexity dichotomy
- Conjunctive-query containment and constraint satisfaction
- On Boolean primitive positive clones
- A new tractable class of constraint satisfaction problems
- Majority constraints have bounded pathwidth duality
- The complexity of general-valued CSPs
- \(H\)-coloring degree-bounded (acyclic) digraphs
- Maltsev digraphs have a majority polymorphism
- \(H\)-coloring dichotomy revisited
- On the intricacy of combinatorial construction problems
- The complexity of constraint satisfaction games and QCSP
- A new line of attack on the dichotomy conjecture
- Algorithmic combinatorics based on slicing posets
- A combinatorial constraint satisfaction problem dichotomy classification conjecture
- Term equation satisfiability over finite algebras
- Domain permutation reduction for constraint satisfaction problems
- The complexity of soft constraint satisfaction
- A strong Mal'cev condition for locally finite varieties omitting the unary type
- Strong partial clones and the time complexity of SAT problems
- Combinatorial problems raised from 2-semilattices
- Bounded Tree-Width and CSP-Related Problems
- Basics of Galois Connections
- Digraph matrix partitions and trigraph homomorphisms
- The constraint satisfaction problem and universal algebra
- Existentially restricted quantified constraint satisfaction
- Hard constraint satisfaction problems have hard gaps at location 1
- Varieties with few subalgebras of powers
- Universal algebra and hardness results for constraint satisfaction problems
- Generalising submodularity and Horn clauses: Tractable optimization problems defined by tournament pair multimorphisms
- Supermodular functions and the complexity of MAX CSP
- On the Computational Complexity of Monotone Constraint Satisfaction Problems
- On solvability of systems of polynomial equations
- Enumerating all solutions of a Boolean CSP by non-decreasing weight
- Periodic constraint satisfaction problems: Tractable subclasses
- An algebraic formulation of Thurston’s combinatorial equivalence
- Minimization of locally defined submodular functions by optimal soft arc consistency
- Partial Polymorphisms and Constraint Satisfaction Problems
- Rigid binary relations on a 4-element domain
- Gap theorems for robust satisfiability: Boolean CSPs and beyond
- The number of clones determined by disjunctions of unary relations
- Title not available (Why is that?)
- The expressive power of valued constraints: Hierarchies and collapses
- Generalisations of matrix partitions: complexity and obstructions
- Conditional dichotomy of Boolean ordered promise CSPs
- Unifying the three algebraic approaches to the CSP via minimal Taylor algebras
- List homomorphism problems for signed trees
- Promise constraint satisfaction: algebraic structure and a symmetric Boolean dichotomy
- Title not available (Why is that?)
- Time complexity of constraint satisfaction via universal algebra
- Title not available (Why is that?)
- The complexity of conservative valued CSPs
- Combinatorial Structures on van der Waerden sets
- A note on some collapse results of valued constraints
- Title not available (Why is that?)
- Constants and finite unary relations in qualitative constraint reasoning
- Quantified Constraints in Twenty Seventeen
- Circuit satisfiability and constraint satisfaction around Skolem arithmetic
- Algebras for combinatorial search
- Relating the Time Complexity of Optimization Problems in Light of the Exponential-Time Hypothesis
- Computing a partition function of a generalized pattern-based energy over a semiring
- Title not available (Why is that?)
- Title not available (Why is that?)
- CLAP: A New Algorithm for Promise CSPs
- Ideal membership problem over 3-element CSPs with dual discriminator polymorphism
- The \(C_{k}\)-extended graft construction
- On the general coloring problem
- Complexity classification transfer for CSPs via algebraic products
- Necessary conditions for tractability of valued CSPs
This page was built for publication: On the algebraic structure of combinatorial problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1276253)
