Showing cs.DSShow all
3 papers · 1 filter
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 -Tour defined within this model, the objective to fi…
cs.DS2024
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…
cs.DS2024
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…