Parameterized complexity of the workflow satisfiability problem

DOI10.1007/978-981-10-6147-9_5MaRDI QIDQ4689628zbMATH OpenOpenAlexFDO

Authors

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

Mathematics Subject Classification ID

Management decision making, including multiple objectives (90B50)

Recommendations

• Fixed-parameter tractability of workflow satisfiability in the presence of seniority constraints
• Iterative Plan Construction for the Workflow Satisfiability Problem
• On the workflow satisfiability problem with class-independent constraints
• Pattern backtracking algorithm for the workflow satisfiability problem with user-independent constraints
• Algorithms for the workflow satisfiability problem engineered for counting constraints

Cites work

• A new tractable class of constraint satisfaction problems
• A Simple Algorithm for Mal'tsev Constraints
• An optimal coarse-grained arc consistency algorithm
• Building tractable disjunctive constraints
• Characterising tractable constraints
• Classifying the Complexity of Constraints Using Finite Algebras
• Comments on Mohr and Henderson's path consistency algorithm
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Constraint Satisfaction with Countable Homogeneous Templates
• Engineering algorithms for workflow satisfiability problem with user-independent constraints
• Fixed-parameter tractability of workflow satisfiability in the presence of seniority constraints
• Fundamentals of parameterized complexity
• Handbook of constraint programming.
• Iterative Plan Construction for the Workflow Satisfiability Problem
• On a Problem of Sidon in Additive Number Theory, and on some Related Problems
• On the complexity of k-SAT
• On the CSP Dichotomy Conjecture
• On the workflow satisfiability problem with class-independent constraints
• Parameterized algorithms
• Pattern backtracking algorithm for the workflow satisfiability problem with user-independent constraints
• Polynomial kernels and user reductions for the workflow satisfiability problem
• Reasoning about temporal relations, the tractable subalgebras of Allen's interval algebra
• Set partitioning via inclusion-exclusion
• The complexity of satisfiability problems
• Tight lower bounds for the workflow satisfiability problem based on the strong exponential time hypothesis
• Tractable constraints on ordered domains
• Which problems have strongly exponential complexity?

Cited in

(6)

• On the satisfiability of authorization requirements in business process
• Iterative Plan Construction for the Workflow Satisfiability Problem
• Polynomial kernels and user reductions for the workflow satisfiability problem
• Polynomial kernels and user reductions for the workflow satisfiability problem
• On the workflow satisfiability problem with class-independent constraints
• Fixed-parameter tractability of workflow satisfiability in the presence of seniority constraints

Describes a project that uses

Uses Software

• Sat4j

This page was built for publication: Parameterized complexity of the workflow satisfiability problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4689628)