1 citations · 1 across the 9 of their papers we have counts for
13 papers
A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach
Many problems are known to be solvable in subexponential parameterized time when the input graph is planar. The bidimensionality framework of Demaine, Fomin, Hajiaghay, and Thiliko…
Line Cover and Related Problems
Matthias Bentert, Fedor v. Fomin, Petr A. Golovach +4
We study extensions of the classic \emph{Line Cover} problem, which asks whether a set of points in the plane can be covered using lines. Line Cover is known to be NP-hard,…
The Directed Disjoint Paths Problem with Congestion
Matthias Bentert, Dario Cavallaro, Amelie Heindl +3
The classic result by Fortune, Hopcroft, and Wyllie [TCS~'80] states that the directed disjoint paths problem is NP-complete even for two pairs of terminals. Extending this well-kn…
Fault-Tolerant Matroid Bases
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +1
We investigate the problem of constructing fault-tolerant bases in matroids. Given a matroid M and a redundancy parameter k, a k-fault-tolerant basis is a minimum-size set of eleme…
When does FTP become FPT?
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +1
In the problem Fault-Tolerant Path (FTP), we are given an edge-weighted directed graph G = (V, E), a subset U \subseteq E of vulnerable edges, two vertices s, t \in V, and integers…
When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +2
Distance geometry explores the properties of distance spaces that can be exactly represented as the pairwise Euclidean distances between points in (), or e…
Planar Network Diversion
Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin +1
Network Diversion is a graph problem that has been extensively studied in both the network-analysis and operations-research communities as a measure of how robust a network is agai…
Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
Matthias Bentert, Fedor V. Fomin, Tanmay Inamdar +1
In this paper, we begin the exploration of vertex-ordering problems through the lens of exponential-time approximation algorithms. In particular, we ask the following question: Can…
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…
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…
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…
Finding a Sparse Connected Spanning Subgraph in a non-Uniform Failure Model
Matthias Bentert, Jannik Schestag, Frank Sommer
We study a generalization of the classic Spanning Tree problem that allows for a non-uniform failure model. More precisely, edges are either \emph{safe} or \emph{unsafe} and we ass…
Two-sets cut-uncut on planar graphs
Matthias Bentert, Pål Grønås Drange, Fedor V. Fomin +2
We study the following Two-Sets Cut-Uncut problem on planar graphs. Therein, one is given an undirected planar graph and two sets of vertices and . The question is, what…