On the algebraic structure of combinatorial problems

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

• scientific article; zbMATH DE number 1670830
• Classifying the Complexity of Constraints Using Finite Algebras
• Asking the Metaquestions in Constraint Tractability
• An Algebraic Model for Combinatorial Problems

zbMATH Keywords

graph isomorphismsatisfiabilitygraph colorability

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

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)

• 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
• Galois connections for patterns: an algebra of labelled graphs
• A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties
• Exploring new topologies for the theory of clones
• Title not available (Why is that?)
• SDPs and robust satisfiability of promise CSP
• Approximability of the Maximum Solution Problem for Certain Families of Algebras
• Quantaloidal approach to constraint satisfaction
• Hybrid VCSPs with crisp and valued conservative templates
• Title not available (Why is that?)
• Learnability of solutions to conjunctive queries
• Absorption in universal algebra and CSP
• Algebra and the complexity of digraph CSPs: a survey
• Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
• The Expressive Power of Valued Constraints: Hierarchies and Collapses
• Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint
• A practical algorithm for structure embedding
• Commutative idempotent groupoids and the constraint satisfaction problem.
• Constraint satisfaction problem: what makes the problem easy
• On the algebraic combinatorics of injections
• Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations
• 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

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)