4 papers
Faster Exponential Algorithms for Multi-Machine Scheduling Problems
Anubhav Dhar, Anita Dürr, Ahmed Ghazy +2
Minimizing the weighted completion times () and weighted number of tardy jobs () on multiple identical machines are two classical NP-har…
Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth- Deletion
Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann +1
For a constant , Pathwidth- Deletion is the problem of deciding whether, for a given graph and integer , there is a set of size at most su…
A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
Jakob Greilhuber, Roohani Sharma
In this work we study a classic generalization of the Vertex Cover (VC) problem, called the Component Order Connectivity (COC) problem. In COC, given an undirected graph , integ…
The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
Jakob Greilhuber, Dániel Marx
For fixed sets of non-negative integers, the -domination framework introduced by Telle [Nord. J. Comput. 1994] captures many classical graph problems. For a graph $G…