activity
20232026
most citedTight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths

1 citations · 1 across the 9 of their papers we have counts for

collaborators
Showing 2024Show all

3 papers · 1 filter

cs.DS2024

Packing Short Cycles

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +6

Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of v…

cs.DS2024

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut

Matthias Bentert, Fedor V. Fomin, Fanny Hauser +1

In Two-Sets Cut-Uncut, we are given an undirected graph and two terminal sets and . The task is to find a minimum cut in (if there is any) separating f…

cs.DS2024★ 1 cited

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths

Matthias Bentert, Fedor V. Fomin, Petr A. Golovach

We examine the possibility of approximating Maximum Vertex-Disjoint Shortest Paths. In this problem, the input is an edge-weighted (directed or undirected) -vertex graph alo…