1 citations · 1 across the 9 of their papers we have counts for
7 papers · 1 filter
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…