Parameterized complexity classification for interval constraints
From MaRDI portal
Cites work
- A dichotomy theorem for nonuniform CSPs
- A proof of the CSP dichotomy conjecture
- Almost 2-SAT is fixed-parameter tractable
- Almost consistent systems of linear equations
- Classifying the Complexity of Constraints Using Finite Algebras
- Complexity and algorithms for reasoning about time
- Complexity of infinite-domain constraint satisfaction
- Constant ratio fixed-parameter approximation of the edge multicut problem
- Directed flow-augmentation
- Directed subset feedback vertex set is fixed-parameter tractable
- Fixed-parameter Approximability of Boolean MinCSPs
- Flow-augmentation. III: Complexity dichotomy for Boolean CSPs parameterized by the number of unsatisfied constraints
- Hitting long directed cycles is fixed-parameter tractable
- scientific article; zbMATH DE number 5485529 (Why is no real title available?)
- scientific article; zbMATH DE number 5485536 (Why is no real title available?)
- scientific article; zbMATH DE number 7788352 (Why is no real title available?)
- Linear time parameterized algorithms for \textsc{Subset Feedback Vertex Set}
- Maintaining knowledge about temporal intervals
- Minimal-change integrity maintenance using tuple deletions
- Non-dichotomies in Constraint Satisfaction Complexity
- On directed feedback vertex set parameterized by treewidth
- On the parameterized complexity of symmetric directed multicut
- On the power of unique 2-prover 1-round games
- Parameterized algorithms
- Parameterized algorithms for generalizations of directed feedback vertex set
- Parameterized complexity classification for interval constraints
- Parameterized complexity of satisfying almost all linear equations over \(\mathbb F_2\)
- Reasoning about temporal relations, the tractable subalgebras of Allen's interval algebra
- Simultaneous feedback edge set: a parameterized perspective
- Simultaneous feedback vertex set: a parameterized perspective
- Solving hard cut problems via flow-augmentation
- Temporal constraint networks
- The approximability of constraint satisfaction problems
- The complexity of general-valued CSPs
- The complexity of temporal constraint satisfaction problems
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- Towards a polynomial kernel for directed feedback vertex set
- When recursion is better than iteration: a linear-time algorithm for acyclicity with few error vertices
Cited in
(5)- Almost consistent systems of linear equations
- Parameterized complexity classification for interval constraints
- Flow-augmentation. III: Complexity dichotomy for Boolean CSPS parameterized by the number of unsatisfied constraints
- Parameterized complexity of MinCSP over the point algebra
- Parameterized approximability for modular linear equations
This page was built for publication: Parameterized complexity classification for interval constraints
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6926199)
