Ahmed Ghazy

collaborators

4 papers

cs.DS2026

Faster Exponential Algorithms for Multi-Machine Scheduling Problems

Anubhav Dhar, Anita Dürr, Ahmed Ghazy +2

Minimizing the weighted completion times ( $P ∣∣ Σ w_{j} C_{j}$ ) and weighted number of tardy jobs ( $P ∣∣ Σ w_{j} U_{j}$ ) on multiple identical machines are two classical NP-har…

cs.DS2026

Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth- $η$ Deletion

Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann +1

For a constant $η \geq 0$ , Pathwidth- $η$ Deletion is the problem of deciding whether, for a given graph $G$ and integer $k$ , there is a set $S \subseteq V (G)$ of size at most $k$ su…

cs.DS2025

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 $I^´$ -Tour defined within this model, the objective to f…

cs.DS2025

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $I^´$ -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…

Faster Exponential Algorithms for Multi-Machine Scheduling Problems

Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth-η Deletion

From Chinese Postman to Salesman and Beyond II: Inapproximability and Parameterized Complexity

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours I^´-Covering All Points on All Edges

Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth- $η$ Deletion

From Chinese Postman to Salesman and Beyond I: Approximating Shortest Tours $I^´$ -Covering All Points on All Edges