On the public citation graph

Constraint Solving via Fractional Edge Covers

https://doi.org/10.1145/2636918
0 signed · 153 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.20025openalex-snapshot
Marshals, monotone marshals, and hypertree‐width
inferredcites →https://doi.org/10.1002/jgt.v47:4openalex-snapshot
inferredcites →https://doi.org/10.1006/jcss.2001.1774openalex-snapshot
Which Problems Have Strongly Exponential Complexity?
inferredcites →https://doi.org/10.1006/jcss.2001.1809openalex-snapshot
Hypertree Decompositions and Tractable Queries
inferredcites →https://doi.org/10.1006/jctb.1993.1027openalex-snapshot
Graph Searching and a Min-Max Theorem for Tree-Width
inferredcites →https://doi.org/10.1007/11564751_15openalex-snapshot
Beyond Hypertree Width: Decomposition Methods Without Decompositions
inferredcites →https://doi.org/10.1007/11604686_1openalex-snapshot
Hypertree Decompositions: Structure, Algorithms, and Applications
inferredcites →https://doi.org/10.1007/bf02780332openalex-snapshot
On the number of copies of one hypergraph in another
inferredcites →https://doi.org/10.1007/s00224-009-9248-9openalex-snapshot
Tractable Structures for Constraint Satisfaction with Truth Tables
inferredcites →https://doi.org/10.1016/0004-3702(89)90037-4openalex-snapshot
Tree clustering for constraint networks
inferredcites →https://doi.org/10.1016/0097-3165(86)90019-1openalex-snapshot
Some intersection theorems for ordered sets and graphs
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.2007.08.001openalex-snapshot
A unified theory of structural tractability for constraint satisfaction problems
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.jcss.2011.09.006openalex-snapshot
Enumerating homomorphisms
inferredcites →https://doi.org/10.1016/s0004-3702(00)00078-3openalex-snapshot
A comparison of structural CSP decomposition methods
inferredcites →https://doi.org/10.1016/s0022-0000(03)00030-8openalex-snapshot
Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width
inferredcites →https://doi.org/10.1016/s0924-6509(09)x7013-3openalex-snapshot
Graphs and Hypergraphs
inferredcites →https://doi.org/10.1017/cbo9780511662119openalex-snapshot
Surveys in Combinatorics, 1997
inferredcites →https://doi.org/10.1017/cbo9780511662119.006openalex-snapshot
Tree Width and Tangles: A New Connectivity Measure and Some Applications
inferredcites →https://doi.org/10.1108/ir.1999.04926fae.001openalex-snapshot
Lecture Notes in Computer Science 1205
inferredcites →https://doi.org/10.1137/060673898openalex-snapshot
Closest Substring Problems with Small Distances
inferredcites →https://doi.org/10.1137/080743226openalex-snapshot
Approximating Width Parameters of Hypergraphs with Excluded Minors
inferredcites →https://doi.org/10.1137/110859440openalex-snapshot
Size Bounds and Query Plans for Relational Joins
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/1206035.1206036openalex-snapshot
The complexity of homomorphism and constraint satisfaction problems seen from the other side
inferredcites →https://doi.org/10.1145/1568318.1568320openalex-snapshot
Generalized hypertree decompositions: NP-hardness and tractable variants
inferredcites →https://doi.org/10.1145/1721837.1721845openalex-snapshot
Approximating fractional hypertree width
inferredcites →https://doi.org/10.1145/1970398.1970400openalex-snapshot
Complexity of conservative constraint satisfaction problems
inferredcites →https://doi.org/10.1145/210332.210337openalex-snapshot
Color-coding
inferredcites →https://doi.org/10.1145/2213556.2213565openalex-snapshot
Worst-Case Optimal Join Algorithms
inferredcites →https://doi.org/10.1145/2220357.2220363openalex-snapshot
Size and Treewidth Bounds for Conjunctive Queries
inferredcites →https://doi.org/10.1145/2402.322390openalex-snapshot
Degrees of acyclicity for hypergraphs and relational database schemes
inferredcites →https://doi.org/10.1145/2535926openalex-snapshot
Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
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/380752.380867openalex-snapshot
When is the evaluation of conjunctive queries tractable?
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.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.2139/ssrn.4132993openalex-extracted
inferred← citeshttps://doi.org/10.1007/978-3-030-30048-7_12openalex-snapshot
A Join-Based Hybrid Parameter for Constraint Satisfaction
inferred← citeshttps://doi.org/10.1007/978-3-030-58475-7_17openalex-snapshot
Breaking Symmetries with RootClique and LexTopSort
inferred← citeshttps://doi.org/10.1007/978-3-030-58942-4_1openalex-snapshot
The HyperTrac Project: Recent Progress and Future Research Directions on Hypergraph Decompositions
inferred← citeshttps://doi.org/10.1007/978-3-031-00123-9_2openalex-snapshot
Cross-Model Conjunctive Queries over Relation and Tree-Structured Data
inferred← citeshttps://doi.org/10.1007/978-3-319-30024-5_10openalex-snapshot
The Challenge of Optional Matching in SPARQL
inferred← citeshttps://doi.org/10.1007/978-3-319-39817-4_11openalex-snapshot
Fractional Edge Cover Number of Model RB
inferred← citeshttps://doi.org/10.1007/978-3-319-61470-0openalex-snapshot
Graph Transformation
inferred← citeshttps://doi.org/10.1007/978-3-319-61893-7_15openalex-snapshot
Structural Decomposition Methods: Key Notions and Database Applications
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-319-98334-9_8openalex-snapshot
An SMT Approach to Fractional Hypertree Width
inferred← citeshttps://doi.org/10.1007/s00224-018-9901-2openalex-snapshot
Evaluating Datalog via Tree Automata and Cycluits
inferred← citeshttps://doi.org/10.1007/s00224-023-10128-wopenalex-snapshot
Computing a Partition Function of a Generalized Pattern-Based Energy over a Semiring
inferred← citeshttps://doi.org/10.1007/s00453-022-00932-0openalex-snapshot
Finding Optimal Triangulations Parameterized by Edge Clique Cover
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-022-09332-1openalex-snapshot
Fast and parallel decomposition of constraint satisfaction problems
inferred← citeshttps://doi.org/10.1016/j.artint.2019.103180openalex-snapshot
Coalitional games induced by matching problems: Complexity and islands of tractability for the Shapley value
inferred← citeshttps://doi.org/10.1016/j.artint.2023.104015openalex-snapshot
Computing optimal hypertree decompositions with SAT
inferred← citeshttps://doi.org/10.1016/j.ic.2016.11.004openalex-snapshot
Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems
inferred← citeshttps://doi.org/10.1016/j.ins.2026.124270openalex-snapshot
Conflict hypergraphs for distinguishing feature selection: Structural limits and exact optimization
inferred← citeshttps://doi.org/10.1016/j.jcss.2017.11.005openalex-snapshot
Tree projections and constraint optimization problems: Fixed-parameter tractability and parallel algorithms
inferred← citeshttps://doi.org/10.1016/j.jcss.2021.01.003openalex-snapshot
Regularizing conjunctive features for classification
inferred← citeshttps://doi.org/10.1016/j.tcs.2022.12.002openalex-snapshot
Tractability beyond β-acyclicity for conjunctive queries with negation and SAT
inferred← citeshttps://doi.org/10.1016/j.tcs.2023.114204openalex-snapshot
Fractional covers of hypergraphs with bounded multi-intersection
inferred← citeshttps://doi.org/10.1109/access.2020.3015654openalex-snapshot
On Quasi Cycles in Hypergraph Databases
inferred← citeshttps://doi.org/10.1109/focs61266.2024.00053openalex-snapshot
Efficient Approximation of Fractional Hypertree Width
inferred← citeshttps://doi.org/10.1109/icde53745.2022.00299openalex-snapshot
Toward Responsive DBMS: Optimal Join Algorithms, Enumeration, Factorization, Ranking, and Dynamic Programming
inferred← citeshttps://doi.org/10.1109/lics.2019.8785660openalex-snapshot
Point-width and Max-CSPs
inferred← citeshttps://doi.org/10.1109/lics56636.2023.10175769openalex-snapshot
Applications of Information Inequalities to Database Theory Problems
inferred← citeshttps://doi.org/10.1137/1.9781611975031.16openalex-snapshot
Minor-matching hypertree width
inferred← citeshttps://doi.org/10.1137/16m1090272openalex-snapshot
The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems
inferred← citeshttps://doi.org/10.1145/2213556.2213565openalex-snapshot
Worst-Case Optimal Join Algorithms
inferred← citeshttps://doi.org/10.1145/2535926openalex-snapshot
Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
inferred← citeshttps://doi.org/10.1145/2745754.2745767openalex-snapshot
Efficient Evaluation and Approximation of Well-designed Pattern Trees
inferred← citeshttps://doi.org/10.1145/2902251.2902280openalex-snapshot
FAQ
inferred← citeshttps://doi.org/10.1145/2902251.2902293openalex-snapshot
AJAR
inferred← citeshttps://doi.org/10.1145/2902251.2902309openalex-snapshot
Hypertree Decompositions
inferred← citeshttps://doi.org/10.1145/3034786.3056105openalex-snapshot
What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?
inferred← citeshttps://doi.org/10.1145/3137586.3137588openalex-snapshot
Semantic Optimization in Tractable Classes of Conjunctive Queries
inferred← citeshttps://doi.org/10.1145/3196959.3196960openalex-snapshot
In-Database Learning with Sparse Tensors
inferred← citeshttps://doi.org/10.1145/3196959.3196962openalex-snapshot
General and Fractional Hypertree Decompositions
inferred← citeshttps://doi.org/10.1145/3233983openalex-snapshot
Efficient Evaluation and Static Analysis for Well-Designed Pattern Trees with Projection
inferred← citeshttps://doi.org/10.1145/3292048.3292050openalex-snapshot
Constraint satisfaction problems
inferred← citeshttps://doi.org/10.1145/3294052.3319678openalex-snapshot
Ranked Enumeration of Minimal Triangulations
inferred← citeshttps://doi.org/10.1145/3294052.3319683openalex-snapshot
HyperBench
inferred← citeshttps://doi.org/10.1145/3294052.3319694openalex-snapshot
On Functional Aggregate Queries with Additive Inequalities
inferred← citeshttps://doi.org/10.1145/3294052.3319698openalex-snapshot
Instance and Output Optimal Parallel Algorithms for Acyclic Joins
inferred← citeshttps://doi.org/10.1145/3301297openalex-snapshot
Solving Graph Problems via Potential Maximal Cliques
inferred← citeshttps://doi.org/10.1145/3318464.3383132openalex-snapshot
Optimal Join Algorithms Meet Top-k
inferred← citeshttps://doi.org/10.1145/3375395.3387645openalex-snapshot
Bag Query Containment and Information Theory
inferred← citeshttps://doi.org/10.1145/3375395.3387664openalex-snapshot
The Impact of Negation on the Complexity of the Shapley Value in Conjunctive Queries
inferred← citeshttps://doi.org/10.1145/3385634.3385636openalex-snapshot
Constant delay enumeration for conjunctive queries
inferred← citeshttps://doi.org/10.1145/3389390openalex-snapshot
Approximate Counting CSP Seen from the Other Side
inferred← citeshttps://doi.org/10.1145/3409447openalex-snapshot
Point-Width and Max-CSPs
inferred← citeshttps://doi.org/10.1145/3426865openalex-snapshot
Functional Aggregate Queries with Additive Inequalities
inferred← citeshttps://doi.org/10.1145/3440015openalex-snapshot
HyperBench
inferred← citeshttps://doi.org/10.1145/3448016.3457314openalex-snapshot
Vertex-centric Parallel Computation of SQL Queries
inferred← citeshttps://doi.org/10.1145/3452021.3458308openalex-snapshot
Tractability Beyond ß-Acyclicity for Conjunctive Queries with Negation
inferred← citeshttps://doi.org/10.1145/3457374openalex-snapshot
Complexity Analysis of Generalized and Fractional Hypertree Decompositions
inferred← citeshttps://doi.org/10.1145/3472391openalex-snapshot
Bag Query Containment and Information Theory
inferred← citeshttps://doi.org/10.1145/3514221.3517893openalex-snapshot
Computing Complex Temporal Join Queries Efficiently
inferred← citeshttps://doi.org/10.1145/3517804.3524152openalex-snapshot
The Complexity of Conjunctive Queries with Degree 2
inferred← citeshttps://doi.org/10.1145/3517804.3524156openalex-snapshot
The Complexity of Boolean Conjunctive Queries with Intersection Joins
inferred← citeshttps://doi.org/10.1145/3517804.3526231openalex-snapshot
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
inferred← citeshttps://doi.org/10.1145/3517804.3526234openalex-snapshot
Tight Fine-Grained Bounds for Direct Access on Join Queries
inferred← citeshttps://doi.org/10.1145/3564246.3585204openalex-snapshot
The Complexity of Pattern Counting in Directed Graphs, Parameterised by the Outdegree
inferred← citeshttps://doi.org/10.1145/3584372.3588676openalex-snapshot
Guaranteeing the Õ(AGM/OUT) Runtime for Uniform Sampling and Size Estimation over Joins
inferred← citeshttps://doi.org/10.1145/3622758openalex-snapshot
Proceedings of the 2023 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software
inferred← citeshttps://doi.org/10.1145/3622758.3622887openalex-snapshot
Scalable Spreadsheet-Driven End-User Applications with Incremental Computation
inferred← citeshttps://doi.org/10.1145/3651614openalex-snapshot
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
inferred← citeshttps://doi.org/10.1145/3689634openalex-snapshot
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
inferred← citeshttps://doi.org/10.1145/3712311.3712313openalex-snapshot
Pessimistic Cardinality Estimation
inferred← citeshttps://doi.org/10.1145/3722234.3725822openalex-snapshot
Querying Graph Data: Where We Are and Where To Go
inferred← citeshttps://doi.org/10.1145/3725233openalex-snapshot
Efficient Algorithms for Cardinality Estimation and Conjunctive Query Evaluation With Simple Degree Constraints
inferred← citeshttps://doi.org/10.1145/3725235openalex-snapshot
Fast Matrix Multiplication meets the Submodular Width
inferred← citeshttps://doi.org/10.1145/3725251openalex-snapshot
Soft and Constrained Hypertree Width
inferred← citeshttps://doi.org/10.1145/3725296openalex-snapshot
Fast Hypertree Decompositions via Linear Programming: Fractional and Generalized
inferred← citeshttps://doi.org/10.1145/3725423openalex-snapshot
Yannakakis+: Practical Acyclic Query Evaluation with Theoretical Guarantees
inferred← citeshttps://doi.org/10.1145/3734517openalex-snapshot
Any-k Algorithms for Enumerating Ranked Answers to Conjunctive Queries
inferred← citeshttps://doi.org/10.1145/3767717openalex-snapshot
Query Answering Under Volume-Based Diversity Functions
inferred← citeshttps://doi.org/10.1145/3767719openalex-snapshot
The Space-Time Complexity of Sum-Product Queries
inferred← citeshttps://doi.org/10.1145/3771726openalex-snapshot
Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity
inferred← citeshttps://doi.org/10.1145/3788852.3805595openalex-snapshot
Query Optimization and Evaluation via Information Theory
inferred← citeshttps://doi.org/10.1145/3793217.3793219openalex-snapshot
Split Theorems for Join Reporting and Sampling
inferred← citeshttps://doi.org/10.1145/3799232openalex-snapshot
FPT Approximation of Generalised Hypertree Width for Bounded Intersection Hypergraphs
inferred← citeshttps://doi.org/10.1145/3801904openalex-snapshot
Jaguar: A Primal Algorithm for Conjunctive Query Evaluation in Submodular-Width Time
inferred← citeshttps://doi.org/10.14778/3397230.3397250openalex-snapshot
Optimal algorithms for ranked enumeration of answers to full conjunctive queries
inferred← citeshttps://doi.org/10.14778/3407790.3407840openalex-snapshot
Distributed subgraph counting
inferred← citeshttps://doi.org/10.14778/3704965.3704973openalex-snapshot
A Branch-&-Bound Algorithm for Fractional Hypertree Decomposition
inferred← citeshttps://doi.org/10.14778/3718057.3718068openalex-snapshot
Avoiding Materialisation for Guarded Aggregate Queries
inferred← citeshttps://doi.org/10.14778/3819518.3819552openalex-snapshot
Subgraph Enumeration: Beyond Tree Decomposition
inferred← citeshttps://doi.org/10.1609/aaai.v35i7.16788openalex-snapshot
Knowledge-Base Degrees of Inconsistency: Complexity and Counting
inferred← citeshttps://doi.org/10.1609/aaai.v38i8.28657openalex-snapshot
Encoding Constraints as Binary Constraint Networks Satisfying BTP
inferred← citeshttps://doi.org/10.17760/d20316246openalex-snapshot
Any-k evaluation of conjunctive queries and its application to graph pattern matching
inferred← citeshttps://doi.org/10.24963/ijcai.2019/156openalex-snapshot
Enumerating Potential Maximal Cliques via SAT and ASP
inferred← citeshttps://doi.org/10.4204/eptcs.360.4openalex-snapshot
The Programming of Algebra
inferred← citeshttps://doi.org/10.4230/lipics.icdt.2018.16openalex-snapshot
Covers of Query Results
inferred← citeshttps://doi.org/10.4230/lipics.icdt.2019.21openalex-snapshot
Boolean Tensor Decomposition for Conjunctive Queries with Negation
inferred← citeshttps://doi.org/10.4230/lipics.icdt.2019.4openalex-snapshot
Counting Triangles under Updates in Worst-Case Optimal Time
inferred← citeshttps://doi.org/10.4230/lipics.icdt.2021.3openalex-snapshot
Box Covers and Domain Orderings for Beyond Worst-Case Join Processing
inferred← citeshttps://doi.org/10.4230/lipics.mfcs.2019.58openalex-snapshot
Constant delay enumeration with FPT-preprocessing for conjunctive queries of bounded submodular width
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.1504.04044openalex-snapshot
FAQ: Questions Asked Frequently
inferred← citeshttps://doi.org/10.48550/arxiv.1508.07532openalex-snapshot
Aggregations over Generalized Hypertree Decompositions
inferred← citeshttps://doi.org/10.48550/arxiv.1611.01090openalex-snapshot
General and Fractional Hypertree Decompositions: Hard and Easy Cases
inferred← citeshttps://doi.org/10.48550/arxiv.1803.09930openalex-snapshot
Worst-Case Optimal Join Algorithms: Techniques, Results, and Open Problems
inferred← citeshttps://doi.org/10.48550/arxiv.1811.08181openalex-snapshot
HyperBench: A Benchmark and Tool for Hypergraphs and Empirical Findings
inferred← citeshttps://doi.org/10.48550/arxiv.1904.07388openalex-snapshot
Point-width and Max-CSPs
inferred← citeshttps://doi.org/10.48550/arxiv.1906.09727openalex-snapshot
Bag Query Containment and Information Theory
inferred← citeshttps://doi.org/10.48550/arxiv.2102.13370openalex-snapshot
Fast Distributed Complex Join Processing
inferred← citeshttps://doi.org/10.70675/86b37144z3689z4cedzb5aez3b420a78f57dopenalex-snapshot
Combined complexity of probabilistic query evaluation
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.