1 citations · 1 across the 3 of their papers we have counts for
5 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…
On the Impact of Stability and the Helly Property on the Dominating Set Problem
Che Cheng, Daniel Mock, Peter Rossmanith
We extend the algorithmic framework of progressive exploration [Fabiański et al., STACS 2019], which yields simple, yet surprisingly general and efficient parameterized algorithms…
Solving Partial Dominating Set and Related Problems Using Twin-Width
Jakub Balabán, Daniel Mock, Peter Rossmanith
Partial vertex cover and partial dominating set are two well-investigated optimization problems. While they are -hard on general graphs, they have been shown to be fixed-…
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…
Tree Coloring: Random Order and Predictions
Fabian Frei, Matthias Gehnen, Dennis Komm +4
Coloring is a notoriously hard problem, and even more so in the online setting, where each arriving vertex has to be colored immediately and irrevocably. Already on trees, which ar…