Parameterized Complexity of the Workflow Satisfiability Problem
From MaRDI portal
Publication:4689628
DOI10.1007/978-981-10-6147-9_5zbMath1397.90206OpenAlexW2963643124MaRDI QIDQ4689628
No author found.
Publication date: 16 October 2018
Published in: Combinatorial Optimization and Graph Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-981-10-6147-9_5
Uses Software
Cites Work
- Unnamed Item
- Polynomial kernels and user reductions for the workflow satisfiability problem
- Fundamentals of parameterized complexity
- Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis
- Comments on Mohr and Henderson's path consistency algorithm
- Characterising tractable constraints
- Which problems have strongly exponential complexity?
- A new tractable class of constraint satisfaction problems
- An optimal coarse-grained arc consistency algorithm
- Iterative Plan Construction for the Workflow Satisfiability Problem
- Building tractable disjunctive constraints
- On the CSP Dichotomy Conjecture
- Engineering Algorithms for Workflow Satisfiability Problem with User-Independent Constraints
- Constraint Satisfaction Problems Solvable by Local Consistency Methods
- Constraint Satisfaction with Countable Homogeneous Templates
- Reasoning about temporal relations
- Pattern Backtracking Algorithm for the Workflow Satisfiability Problem with User-Independent Constraints
- Set Partitioning via Inclusion-Exclusion
- Classifying the Complexity of Constraints Using Finite Algebras
- On the Workflow Satisfiability Problem with Class-independent Constraints
- The complexity of satisfiability problems
- Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints
- A Simple Algorithm for Mal'tsev Constraints
- Parameterized Algorithms
- On a Problem of Sidon in Additive Number Theory, and on some Related Problems
- Tractable constraints on ordered domains
- On the complexity of \(k\)-SAT
