On the public citation graph
Discovering Archipelagos of Tractability for Constraint Satisfaction and Counting
0 signed · 49 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.
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.
What this work says
Outgoing claims: the papers this work cites, builds on, or argues with.
inferredcites →https://doi.org/10.1006/inco.1996.0016openalex-snapshot
Complexity of Generalized Satisfiability Counting Problems
inferredcites →https://doi.org/10.1006/jcss.1995.1087openalex-snapshot
A Dichotomy Theorem for Maximum Generalized Satisfiability Problems
inferredcites →https://doi.org/10.1006/jcss.1999.1626openalex-snapshot
On the Complexity of Database Queries
inferredcites →https://doi.org/10.1007/978-3-319-10428-7_18openalex-snapshot
On Backdoors to Tractable Constraint Languages
inferredcites →https://doi.org/10.1007/978-3-540-70575-8_53openalex-snapshot
The Complexity of the Counting Constraint Satisfaction Problem
inferredcites →https://doi.org/10.1007/978-3-642-31594-7_63openalex-snapshot
Parameterized Tractability of Multiway Cut with Parity Constraints
inferredcites →https://doi.org/10.1007/s00453-007-9130-6openalex-snapshot
An Improved Parameterized Algorithm for the Minimum Node Multiway Cut Problem
inferredcites →https://doi.org/10.1016/0004-3702(94)90021-3openalex-snapshot
Characterising tractable constraints
inferredcites →https://doi.org/10.1016/0020-0255(74)90008-5openalex-snapshot
Networks of constraints: Fundamental properties and applications to picture processing
inferredcites →https://doi.org/10.1016/j.cosrev.2008.10.003openalex-snapshot
Colouring, constraint satisfaction, and complexity
inferredcites →https://doi.org/10.1016/j.ic.2006.09.005openalex-snapshot
Towards a dichotomy theorem for the counting constraint satisfaction problem
inferredcites →https://doi.org/10.1016/j.jcss.2006.04.007openalex-snapshot
Strong computational lower bounds via parameterized complexity
inferredcites →https://doi.org/10.1016/j.jcss.2009.04.002openalex-snapshot
Almost 2-SAT is fixed-parameter tractable
inferredcites →https://doi.org/10.1016/j.orl.2003.10.009openalex-snapshot
Finding odd cycle transversals
inferredcites →https://doi.org/10.1016/j.tcs.2005.10.007openalex-snapshot
Parameterized graph separation problems
inferredcites →https://doi.org/10.1016/s0166-218x(96)00028-5openalex-snapshot
Variable and term removal from Boolean formulae
inferredcites →https://doi.org/10.1109/focs.2013.59openalex-snapshot
Strong Backdoors to Bounded Treewidth SAT
inferredcites →https://doi.org/10.1137/07070440xopenalex-snapshot
The Connectivity of Boolean Satisfiability: Computational and Structural Dichotomies
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/167088.167245openalex-snapshot
Monotone monadic SNP and constraint satisfaction
inferredcites →https://doi.org/10.1145/1970398.1970400openalex-snapshot
Complexity of conservative constraint satisfaction problems
inferredcites →https://doi.org/10.1145/2421119.2421135openalex-snapshot
SIGACT News Complexity Theory Column 76
inferredcites →https://doi.org/10.1145/2450142.2450146openalex-snapshot
The complexity of conservative valued CSPs
inferredcites →https://doi.org/10.1145/2488608.2488697openalex-snapshot
The complexity of finite-valued CSPs
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.1609/aaai.v28i1.9111openalex-snapshot
Backdoors into Heterogeneous Classes of SAT and CSP
inferredcites →https://doi.org/10.4230/lipics.stacs.2012.iopenalex-snapshot
Frontmatter, Foreword, Conference Organization, External Reviewers, Table of Contents
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-86593-1_22openalex-snapshot
Faster FPT Algorithms for Deletion to Pairs of Graph Classes
inferred← citeshttps://doi.org/10.1007/978-3-031-06678-8_1openalex-snapshot
Distance from Triviality 2.0: Hybrid Parameterizations
inferred← citeshttps://doi.org/10.1007/978-3-319-66263-3_2openalex-snapshot
Backdoor Treewidth for SAT
inferred← citeshttps://doi.org/10.1007/s10601-023-09362-3openalex-snapshot
CSP beyond tractable constraint languages
inferred← citeshttps://doi.org/10.1016/j.jcss.2023.03.004openalex-snapshot
Deletion to scattered graph classes II - improved FPT algorithms for deletion to pairs of graph classes
inferred← citeshttps://doi.org/10.1016/j.jcss.2023.05.005openalex-snapshot
Deletion to scattered graph classes I - Case of finite number of graph classes
inferred← citeshttps://doi.org/10.1016/j.jcss.2024.103520openalex-snapshot
SAT backdoors: Depth beats size
inferred← citeshttps://doi.org/10.1016/j.jcss.2024.103597openalex-snapshot
Single-exponential FPT algorithms for enumerating secluded F -free subgraphs and deleting to scattered graph classes
inferred← citeshttps://doi.org/10.1137/1.9781611977073.79openalex-snapshot
Deleting, Eliminating and Decomposing to Hereditary Classes Are All FPT-Equivalent
inferred← citeshttps://doi.org/10.1145/3406325.3451068openalex-snapshot
Vertex deletion parameterized by elimination distance and even less
inferred← citeshttps://doi.org/10.1609/aaai.v31i1.10644openalex-snapshot
Going Beyond Primal Treewidth for (M)ILP
inferred← citeshttps://doi.org/10.1613/jair.1.13787openalex-snapshot
Computational Short Cuts in Infinite Domain Constraint Satisfaction
inferred← citeshttps://doi.org/10.3390/a12120248openalex-snapshot
Solving Integer Linear Programs by Exploiting Variable-Constraint Interactions: A Survey
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.