On the public citation graph

The Structure of Tractable Constraint Satisfaction Problems

0 signed · 69 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.1006/jcss.2001.1809openalex-snapshot
Hypertree Decompositions and Tractable Queries
inferredcites →https://doi.org/10.1007/11564751_15openalex-snapshot
Beyond Hypertree Width: Decomposition Methods Without Decompositions
inferredcites →https://doi.org/10.1007/3-540-29953-xopenalex-snapshot
Parameterized Complexity Theory
inferredcites →https://doi.org/10.1007/3-540-46135-3_21openalex-snapshot
Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics
inferredcites →https://doi.org/10.1007/978-1-4612-0515-9openalex-snapshot
Parameterized Complexity
inferredcites →https://doi.org/10.1007/978-3-662-04565-7openalex-snapshot
Approximation Algorithms
inferredcites →https://doi.org/10.1007/springerreference_57547openalex-snapshot
Approximation Algorithms
inferredcites →https://doi.org/10.1016/0095-8956(90)90132-jopenalex-snapshot
On the complexity of H-coloring
inferredcites →https://doi.org/10.1016/0166-218x(96)00099-6openalex-snapshot
Complexity of tree homomorphisms
inferredcites →https://doi.org/10.1016/j.ejc.2007.04.013openalex-snapshot
Hypertree width and related hypergraph invariants
inferredcites →https://doi.org/10.1016/j.jcss.2010.04.003openalex-snapshot
Constraint satisfaction with succinctly specified relations
inferredcites →https://doi.org/10.1016/j.tcs.2005.09.028openalex-snapshot
H-Coloring dichotomy revisited
inferredcites →https://doi.org/10.1016/s0304-3975(97)00230-2openalex-snapshot
On the algebraic structure of combinatorial problems
inferredcites →https://doi.org/10.1016/s1571-0661(04)00301-9openalex-snapshot
Parameterized Complexity
inferredcites →https://doi.org/10.1016/s1574-6526(06)80012-xopenalex-snapshot
The Complexity of Constraint Languages
inferredcites →https://doi.org/10.1090/s0002-9947-96-01537-1openalex-snapshot
Duality and Polynomial Testing of Tree Homomorphisms
inferredcites →https://doi.org/10.1109/lics.2003.1210072openalex-snapshot
Tractable conservative constraint satisfaction problems
inferredcites →https://doi.org/10.1109/lics.2005.19openalex-snapshot
Generalized Majority-Minority Operations are Tractable
inferredcites →https://doi.org/10.1109/sfcs.2003.1238228openalex-snapshot
The complexity of homomorphism and constraint satisfaction problems seen from the other side
inferredcites →https://doi.org/10.1137/0608024openalex-snapshot
Complexity of Finding Embeddings in a k -Tree
inferredcites →https://doi.org/10.1137/s0097539700376676openalex-snapshot
Classifying the Complexity of Constraints Using Finite Algebras
inferredcites →https://doi.org/10.1137/s0097539793251219openalex-snapshot
A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
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/1109557.1109590openalex-snapshot
Constraint solving via fractional edge covers
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/263867.263489openalex-snapshot
Closure properties of constraints
inferredcites →https://doi.org/10.1145/275487.275511openalex-snapshot
Conjunctive-query containment and constraint satisfaction
inferredcites →https://doi.org/10.1145/321864.321877openalex-snapshot
On the Structure of Polynomial Time Reducibility
inferredcites →https://doi.org/10.1145/380752.380868openalex-snapshot
The complexity of maximal constraint languages
inferredcites →https://doi.org/10.1145/800133.804350openalex-snapshot
The complexity of satisfiability problems
inferredcites →https://doi.org/10.46298/dmtcs.3424openalex-snapshot
Hypertree-Width and Related Hypergraph Invariants
inferredcites →https://doi.org/10.5555/1109557.1109590openalex-snapshot
Constraint solving via fractional edge covers

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-319-21810-6_3openalex-snapshot
Solver performance on tractable CSPs: empirical evaluation
inferred← citeshttps://doi.org/10.1007/978-3-319-44953-1_27openalex-snapshot
The PPSZ Algorithm for Constraint Satisfaction Problems on More Than Two Colors
inferred← citeshttps://doi.org/10.1007/978-3-642-02716-1_1openalex-snapshot
Presenting Constraints
inferred← citeshttps://doi.org/10.1007/978-3-642-15155-2_51openalex-snapshot
Does Treewidth Help in Modal Satisfiability?
inferred← citeshttps://doi.org/10.1007/978-3-642-23786-7_14openalex-snapshot
On Guaranteeing Polynomially Bounded Search Tree Size
inferred← citeshttps://doi.org/10.1007/s00224-009-9248-9openalex-snapshot
Tractable Structures for Constraint Satisfaction with Truth Tables
inferred← citeshttps://doi.org/10.1007/s00453-017-0310-8openalex-snapshot
Complexity and Approximability of Parameterized MAX-CSPs
inferred← citeshttps://doi.org/10.1007/s10601-015-9198-6openalex-snapshot
Tractability in constraint satisfaction problems: a survey
inferred← citeshttps://doi.org/10.1016/j.artint.2010.03.002openalex-snapshot
Generalizing constraint satisfaction on trees: Hybrid tractability and variable elimination
inferred← citeshttps://doi.org/10.1016/j.jcss.2008.02.002openalex-snapshot
Computational complexity of auditing finite attributes in statistical databases
inferred← citeshttps://doi.org/10.1016/j.procs.2021.11.019openalex-snapshot
Instance Optimal Join Size Estimation
inferred← citeshttps://doi.org/10.1093/logcom/exq030openalex-snapshot
Two new homomorphism dualities and lattice operations
inferred← citeshttps://doi.org/10.1109/ase.2013.6693103openalex-snapshot
Measuring the structural complexity of feature models
inferred← citeshttps://doi.org/10.1109/focs.2007.27openalex-snapshot
Can you beat treewidth?
inferred← citeshttps://doi.org/10.1109/lics.2008.19openalex-snapshot
Caterpillar Duality for Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1109/sysose.2015.7151910openalex-snapshot
Contribution to system of systems modeling
inferred← citeshttps://doi.org/10.1109/tsmca.2012.2183350openalex-snapshot
Hypergraph Models for System of Systems Supervision Design
inferred← citeshttps://doi.org/10.1137/1.9781611976489.7openalex-snapshot
Approximate Aggregate Queries Under Additive Inequalities
inferred← citeshttps://doi.org/10.1137/1.9781611976489.8openalex-snapshot
A Relational Gradient Descent Algorithm For Support Vector Machine Training
inferred← citeshttps://doi.org/10.1145/1566445.1566503openalex-snapshot
Tricolorable torus knots are NP-complete
inferred← citeshttps://doi.org/10.1145/1721837.1721845openalex-snapshot
Approximating fractional hypertree width
inferred← citeshttps://doi.org/10.1145/1806689.1806790openalex-snapshot
Tractable hypergraph properties for constraint satisfaction and conjunctive queries
inferred← citeshttps://doi.org/10.1145/2463664.2463671openalex-snapshot
Semantic acyclicity on graph databases
inferred← citeshttps://doi.org/10.1145/2499937.2499939openalex-snapshot
Does Treewidth Help in Modal Satisfiability?
inferred← citeshttps://doi.org/10.1145/2535926openalex-snapshot
Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
inferred← citeshttps://doi.org/10.1145/3434387openalex-snapshot
Fine-Grained Time Complexity of Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1609/aaai.v27i1.8609openalex-snapshot
On the Subexponential Time Complexity of CSP
inferred← citeshttps://doi.org/10.1613/jair.1.14748openalex-snapshot
On the Parallel Parameterized Complexity of MaxSAT Variants
inferred← citeshttps://doi.org/10.1613/jair.3651openalex-snapshot
The Tractability of CSP Classes Defined by Forbidden Patterns
inferred← citeshttps://doi.org/10.1613/jair.4540openalex-snapshot
On the Subexponential-Time Complexity of CSP
inferred← citeshttps://doi.org/10.4086/toc.2010.v006a005openalex-snapshot
inferred← citeshttps://doi.org/10.46298/lmcs-20(1:9)2024openalex-snapshot
Linear Programs with Conjunctive Database Queries
inferred← citeshttps://doi.org/10.48550/arxiv.0911.0801openalex-snapshot
Tractable hypergraph properties for constraint satisfaction and conjunctive queries
inferred← citeshttps://doi.org/10.48550/arxiv.1304.1996openalex-snapshot
On the Subexponential Time Complexity of CSP
inferred← citeshttps://doi.org/10.48550/arxiv.1706.05902openalex-snapshot
Time Complexity of Constraint Satisfaction via Universal Algebra
inferred← citeshttps://doi.org/10.5555/1496770.1496868openalex-snapshot
Approximating fractional hypertree width
inferred← citeshttps://doi.org/10.70675/d53edf6aze8c5z4619zaceez41d6d616e85dopenalex-snapshot
Contribution à la modélisation graphique de système de systèmes
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.