4 papers
Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers
Li-Hsuan Chen, Florent Foucaud, Ling-Ju Hung +3
We study how covering a graph by a small number of shortest or approximately shortest paths/walks constrains its treewidth and pathwidth. A path or walk is -quasi-shortest f…
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…
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…
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…