On the public citation graph

The Dichotomy for Conservative Constraint Satisfaction Problems Revisited

0 signed · 88 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1002/jgt.10073openalex-snapshot
Bi‐arc graphs and the complexity of list homomorphisms
inferredcites →https://doi.org/10.1007/3-540-45022-x_24openalex-snapshot
Constraint Satisfaction Problems and Finite Algebras
inferredcites →https://doi.org/10.1007/s00012-008-2122-9openalex-snapshot
Existence theorems for weakly symmetric operations
inferredcites →https://doi.org/10.1007/s00224-011-9333-8openalex-snapshot
The Complexity of the List Homomorphism Problem for Graphs
inferredcites →https://doi.org/10.1007/s004939970003openalex-snapshot
List Homomorphisms and Circular Arc Graphs
inferredcites →https://doi.org/10.1109/focs.2009.32openalex-snapshot
Constraint Satisfaction Problems of Bounded Width
inferredcites →https://doi.org/10.1109/lics.2003.1210072openalex-snapshot
Tractable conservative constraint satisfaction problems
inferredcites →https://doi.org/10.1109/lics.2007.50openalex-snapshot
Tractability and learnability arising from algebras with few subpowers
inferredcites →https://doi.org/10.1109/lics.2010.34openalex-snapshot
New Conditions for Taylor Varieties and CSP
inferredcites →https://doi.org/10.1137/050628957openalex-snapshot
A Simple Algorithm for Mal'tsev Constraints
inferredcites →https://doi.org/10.1137/070708093openalex-snapshot
The CSP Dichotomy Holds for Digraphs with No Sources and No Sinks (A Positive Answer to a Conjecture of Bang-Jensen and Hell)
inferredcites →https://doi.org/10.1137/080743238openalex-snapshot
Congruence Distributivity Implies Bounded Width
inferredcites →https://doi.org/10.1137/s0097539700376676openalex-snapshot
Classifying the Complexity of Constraints Using Finite Algebras
inferredcites →https://doi.org/10.1137/s0097539794266766openalex-snapshot
The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
inferredcites →https://doi.org/10.1145/1120582.1120584openalex-snapshot
A dichotomy theorem for constraint satisfaction problems on a 3-element set
inferredcites →https://doi.org/10.1145/1374376.1374488openalex-snapshot
Graphs, polymorphisms and the complexity of homomorphism problems
inferredcites →https://doi.org/10.1145/2556646openalex-snapshot
Constraint Satisfaction Problems Solvable by Local Consistency Methods
inferredcites →https://doi.org/10.1145/263867.263489openalex-snapshot
Closure properties of constraints
inferredcites →https://doi.org/10.1145/800133.804350openalex-snapshot
The complexity of satisfiability problems
inferredcites →https://doi.org/10.2168/lmcs-2(4:1)2006openalex-snapshot
Generalized Majority-Minority Operations are Tractable
inferredcites →https://doi.org/10.2168/lmcs-8(1:7)2012openalex-snapshot
Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
inferredcites →https://doi.org/10.4230/lipics.stacs.2010.2467openalex-snapshot
The Complexity of the List Homomorphism Problem for Graphs
inferredcites →https://doi.org/10.4230/lipics.stacs.2010.2493openalex-snapshot
A Dichotomy Theorem for the General Minimum Cost Homomorphism Problem
inferredcites →https://doi.org/10.48550/arxiv.1008.1555openalex-snapshot
The complexity of conservative finite-valued CSPs
inferredcites →https://doi.org/10.5555/2133036.2133167openalex-snapshot
The dichotomy of list homomorphisms for digraphs

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-3-030-43520-2_3openalex-snapshot
Hardness of Network Satisfaction for Relation Algebras with Normal Representations
inferred← citeshttps://doi.org/10.1007/978-3-319-44953-1_9openalex-snapshot
The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable
inferred← citeshttps://doi.org/10.1007/978-3-319-57418-9_13openalex-snapshot
Aggregation of Votes with Multiple Positions on Each Issue
inferred← citeshttps://doi.org/10.1007/978-3-319-77313-1_1openalex-snapshot
Constraint Satisfaction Problems: Complexity and Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-540-70575-8_53openalex-snapshot
The Complexity of the Counting Constraint Satisfaction Problem
inferred← citeshttps://doi.org/10.1007/978-3-642-20712-9_26openalex-snapshot
On the CSP Dichotomy Conjecture
inferred← citeshttps://doi.org/10.1007/978-3-642-22993-0_23openalex-snapshot
An Algebraic Theory of Complexity for Valued Constraints: Establishing a Galois Connection
inferred← citeshttps://doi.org/10.1007/978-3-642-23786-7_18openalex-snapshot
On Minimal Weighted Clones
inferred← citeshttps://doi.org/10.1007/s00012-014-0283-2openalex-snapshot
Decidability of absorption in relational structures of bounded width
inferred← citeshttps://doi.org/10.1007/s00012-015-0358-8openalex-snapshot
CSP for binary conservative relational structures
inferred← citeshttps://doi.org/10.1007/s00012-016-0407-yopenalex-snapshot
Galois theory for semiclones
inferred← citeshttps://doi.org/10.1007/s00012-017-0440-5openalex-snapshot
Deciding absorption in relational structures
inferred← citeshttps://doi.org/10.1007/s00012-024-00865-5openalex-snapshot
Graphs of finite algebras: edges, and connectivity
inferred← citeshttps://doi.org/10.1007/s00037-014-0093-0openalex-snapshot
Testing list H-homomorphisms
inferred← citeshttps://doi.org/10.1007/s10601-015-9198-6openalex-snapshot
Tractability in constraint satisfaction problems: a survey
inferred← citeshttps://doi.org/10.1007/s10601-023-09341-8openalex-snapshot
The smallest hard trees
inferred← citeshttps://doi.org/10.1016/j.artint.2017.12.003openalex-snapshot
Constants and finite unary relations in qualitative constraint reasoning
inferred← citeshttps://doi.org/10.1016/j.ejc.2017.10.001openalex-snapshot
On the complexity of H -coloring for special oriented trees
inferred← citeshttps://doi.org/10.1016/j.ic.2014.08.005openalex-snapshot
Conservative groupoids recognize only regular languages
inferred← citeshttps://doi.org/10.1016/j.ic.2019.104437openalex-snapshot
Constraint Satisfaction Problems over semilattice block Mal'tsev algebras
inferred← citeshttps://doi.org/10.1016/j.jcss.2015.07.004openalex-snapshot
Conservative constraint satisfaction re-revisited
inferred← citeshttps://doi.org/10.1017/9781107337534openalex-snapshot
Complexity of Infinite-Domain Constraint Satisfaction
inferred← citeshttps://doi.org/10.1017/bsl.2015.25openalex-snapshot
THE CONSTRAINT SATISFACTION PROBLEM AND UNIVERSAL ALGEBRA
inferred← citeshttps://doi.org/10.1109/ccc.2012.9openalex-snapshot
Testing List H-homomorphisms
inferred← citeshttps://doi.org/10.1109/focs.2012.25openalex-snapshot
The Power of Linear Programming for Valued CSPs
inferred← citeshttps://doi.org/10.1109/focs.2015.80openalex-snapshot
The Complexity of General-Valued CSPs
inferred← citeshttps://doi.org/10.1109/focs.2017.37openalex-snapshot
A Dichotomy Theorem for Nonuniform CSPs
inferred← citeshttps://doi.org/10.1109/lics.2013.62openalex-snapshot
Why is it Hard to Obtain a Dichotomy for Consistent Query Answering?
inferred← citeshttps://doi.org/10.1109/lics.2017.8005116openalex-snapshot
The complexity of minimal inference problem for conservative constraint languages
inferred← citeshttps://doi.org/10.1109/lics.2017.8005149openalex-snapshot
Constraint satisfaction problems over semilattice block Mal'tsev algebras
inferred← citeshttps://doi.org/10.1137/1.9781611977073.22openalex-snapshot
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
inferred← citeshttps://doi.org/10.1137/130906398openalex-snapshot
An Algebraic Theory of Complexity for Discrete Optimization
inferred← citeshttps://doi.org/10.1137/130945648openalex-snapshot
The Power of Linear Programming for General-Valued CSPs
inferred← citeshttps://doi.org/10.1142/s0218196726500013openalex-snapshot
Network satisfaction problems solved by k -consistency
inferred← citeshttps://doi.org/10.1145/2450142.2450146openalex-snapshot
The complexity of conservative valued CSPs
inferred← citeshttps://doi.org/10.1145/2488608.2488697openalex-snapshot
The complexity of finite-valued CSPs
inferred← citeshttps://doi.org/10.1145/2677161.2677165openalex-snapshot
Constraint satisfaction problem and universal algebra
inferred← citeshttps://doi.org/10.1145/2699912openalex-snapshot
Why Is It Hard to Obtain a Dichotomy for Consistent Query Answering?
inferred← citeshttps://doi.org/10.1145/2933575.2933604openalex-snapshot
Graphs of relational structures
inferred← citeshttps://doi.org/10.1145/2974019openalex-snapshot
The Complexity of Finite-Valued CSPs
inferred← citeshttps://doi.org/10.1145/3292048.3292050openalex-snapshot
Constraint satisfaction problems
inferred← citeshttps://doi.org/10.1145/3301410openalex-snapshot
The Complexity of Minimal Inference Problem for Conservative Constraint Languages
inferred← citeshttps://doi.org/10.1145/3377391.3377393openalex-snapshot
Foundations of Query Answering on Inconsistent Databases
inferred← citeshttps://doi.org/10.1145/3640814openalex-snapshot
Counting List Homomorphisms from Graphs of Bounded Treewidth: Tight Complexity Bounds
inferred← citeshttps://doi.org/10.1609/aaai.v30i1.10432openalex-snapshot
The Meta-Problem for Conservative Mal'tsev Constraints
inferred← citeshttps://doi.org/10.1609/aaai.v35i7.16773openalex-snapshot
Network Satisfaction for Symmetric Relation Algebras with a Flexible Atom
inferred← citeshttps://doi.org/10.1613/jair.1.14195openalex-snapshot
The Complexity of Network Satisfaction Problems for Symmetric Relation Algebras with a Flexible Atom
inferred← citeshttps://doi.org/10.2168/lmcs-11(2:15)2015openalex-snapshot
On absorption in semigroups and $n$-ary semigroups
inferred← citeshttps://doi.org/10.2168/lmcs-8(1:7)2012openalex-snapshot
Absorbing Subalgebras, Cyclic Terms, and the Constraint Satisfaction Problem
inferred← citeshttps://doi.org/10.32920/23459144openalex-snapshot
Expressibility Of Constraint Satisfaction Problems In Extensions Of First-Order Logic
inferred← citeshttps://doi.org/10.32920/23459144.v1openalex-snapshot
Expressibility Of Constraint Satisfaction Problems In Extensions Of First-Order Logic
inferred← citeshttps://doi.org/10.3384/diss.diva-116859openalex-snapshot
On Some Combinatorial Optimization Problems : Algorithms and Complexity
inferred← citeshttps://doi.org/10.3384/diss.diva-164157openalex-snapshot
Applications of Partial Polymorphisms in (Fine-Grained) Complexity of Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.4230/lipics.csl.2017.42openalex-snapshot
An Algebraic Approach to Valued Constraint Satisfaction
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2019.77openalex-snapshot
Testing the Complexity of a Valued CSP Language
inferred← citeshttps://doi.org/10.4230/lipics.icalp.2019.91openalex-snapshot
Toward a Dichotomy for Approximation of $H$-coloring
inferred← citeshttps://doi.org/10.48550/arxiv.1407.1779openalex-snapshot
On the complexity of $\mathbb H$-coloring for special oriented trees
inferred← citeshttps://doi.org/10.48550/arxiv.1408.3690openalex-snapshot
Conservative constraint satisfaction re-revisited
inferred← citeshttps://doi.org/10.48550/arxiv.1604.07063openalex-snapshot
The Dichotomy for Conservative Constraint Satisfaction is Polynomially Decidable
inferred← citeshttps://doi.org/10.48550/arxiv.2006.10239openalex-snapshot
Local structure of idempotent algebras II
inferred← citeshttps://doi.org/10.48550/arxiv.2006.11713openalex-snapshot
Graphs of relational structures: restricted types
inferred← citeshttps://doi.org/10.48550/arxiv.2007.09099openalex-snapshot
A dichotomy theorem for nonuniform CSPs simplified
inferred← citeshttps://doi.org/10.71781/10725openalex-snapshot
Complexité des homomorphismes de graphes avec listes
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.