Showing 2019Show all
3 papers · 1 filter
cs.DS2019
Parameterized Pre-coloring Extension and List Coloring Problems
Gregory Gutin, Diptapriyo Majumdar, Sebastian Ordyniak +1
Golovach, Paulusma and Song (Inf. Comput. 2014) asked to determine the parameterized complexity of the following problems parameterized by : (1) Given a graph , a clique modu…
cs.DS2019
On the Approximate Compressibility of Connected Vertex Cover
Diptapriyo Majumdar, M. S. Ramanujan, Saket Saurabh
The Connected Vertex Cover problem, where the goal is to compute a minimum set of vertices in a given graph which forms a vertex cover and induces a connected subgraph, is a fundam…
cs.DS2019
Bounded and Approximate Strong Satisfiability in Workflows
Jason Crampton, Gregory Gutin, Diptapriyo Majumdar
There has been a considerable amount of interest in recent years in the problem of workflow satisfiability, which asks whether the existence of constraints in a workflow specificat…