Polynomial kernels and user reductions for the workflow satisfiability problem

DOI10.1007/s00453-015-9986-9zbMath1350.68143arXiv1409.7261OpenAlexW2065131193MaRDI QIDQ309799

Magnus Wahlström, Gregory Gutin, Stefan Kratsch

Publication date: 7 September 2016

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1409.7261

zbMATH Keywords

parameterized complexitykernelizationworkflow satisfiability problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05)

Related Items (1)

Parameterized Complexity of the Workflow Satisfiability Problem

Cites Work

• Fundamentals of parameterized complexity
• A Completeness Theory for Polynomial (Turing) Kernelization
• Kernelization – Preprocessing with a Guarantee
• Iterative Plan Construction for the Workflow Satisfiability Problem
• Partial Kernelization for Rank Aggregation: Theory and Experiments
• Engineering Algorithms for Workflow Satisfiability Problem with User-Independent Constraints
• Kernelization Lower Bounds Through Colors and IDs
• Fixed-Parameter Tractability of Workflow Satisfiability in the Presence of Seniority Constraints
• Satisfiability Allows No Nontrivial Sparsification unless the Polynomial-Time Hierarchy Collapses

This page was built for publication: Polynomial kernels and user reductions for the workflow satisfiability problem