3 papers
cs.DS2025
Graph Exploration with Edge Weight Estimates
Matthias Gehnen, Ralf Klasing, Émile Naquin
In the Travelling Salesman Problem, every vertex of an edge-weighted graph has to be visited by an agent who traverses the edges of the graph. In this problem, it is usually assume…
cs.DS2024
Online Unbounded Knapsack
Hans-Joachim Böckenhauer, Matthias Gehnen, Juraj Hromkovič +6
We analyze the competitive ratio and the advice complexity of the online unbounded knapsack problem. An instance is given as a sequence of n items with a size and a value each, and…
cs.DS2024
Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
Dibyayan Chakraborty, Antoine Dailly, Florent Foucaud +1
In this paper, we study a dynamic analogue of the Path Cover problem, which can be solved in polynomial-time in directed acyclic graphs. A temporal digraph has an arc set that chan…