58 citations · 151 across the 35 of their papers we have counts for
4 papers · 1 filter
Chinese Postman Problem on Edge-Colored Multigraphs
Gregory Gutin, Mark Jones, Bin Sheng +2
It is well-known that the Chinese postman problem on undirected and directed graphs is polynomial-time solvable. We extend this result to edge-colored multigraphs. Our result is in…
Tight Lower Bounds for the Workflow Satisfiability Problem Based on the Strong Exponential Time Hypothesis
Gregory Gutin, Magnus Wahlstrom
The Workflow Satisfiability Problem (WSP) asks whether there exists an assignment of authorized users to the steps in a workflow specification, subject to certain constraints on th…
Directed multicut is W[1]-hard, even for four terminal pairs
Marcin Pilipczuk, Magnus Wahlström
We prove that Multicut in directed graphs, parameterized by the size of the cutset, is W[1]-hard and hence unlikely to be fixed-parameter tractable even if restricted to instances…
On the Workflow Satisfiability Problem with Class-Independent Constraints
Jason Crampton, Andrei Gagarin, Gregory Gutin +2
A workflow specification defines sets of steps and users. An authorization policy determines for each user a subset of steps the user is allowed to perform. Other security requirem…