6 papers
Exploring Minimal Blocking Sets for Kernelization Lower Bounds for -Minor Deletion
Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann
For Vertex Cover, a minimal blocking set of a graph is an inclusion-wise minimal vertex set contained in no minimum vertex cover of . Bougeret et al. [SIDMA 2022] showed tha…
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…
From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity
Fabian Frei, Ahmed Ghazy, Tim A. Hartmann +2
A well-studied continuous model of graphs considers each edge as a continuous unit-length interval of points. In the problem -Tour defined within this model, the objective to fi…
From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours -Covering All Points on All Edges
Fabian Frei, Ahmed Ghazy, Tim A. Hartmann +2
A well-studied continuous model of graphs, introduced by Dearing and Francis [Transportation Science, 1974], considers each edge as a continuous unit-length interval of points. For…
Content-Oblivious Leader Election on Rings
Fabian Frei, Ran Gelles, Ahmed Ghazy +1
In content-oblivious computation, n nodes wish to compute a given task over an asynchronous network that suffers from an extremely harsh type of noise, which corrupts the content o…