19 citations · 118 across the 26 of their papers we have counts for
15 papers · 1 filter
Parameterizing Cluster Editing by the Number of Deletions
Vincent Froese, Leon Kellerhals, Frank Sommer +2
In Cluster Editing, we are given a graph and an integer and ask whether at most edge insertions and deletions turn into a disjoint union of cliques. Komusiewicz and…
Parameterized Complexity of Temporal Agony
Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann +1
Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. In order to discover such hierarch…
Computational Complexity of the Interval Ordering Problem
Simeon Pawlowski, Vincent Froese
We study an interval ordering problem introduced by Dürr et al. [Discrete Appl. Math. 2012] which is motivated by applications in bioinformatics. The task is to order a given set o…
Parameterized Algorithms for Computing MAD Trees
Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann +2
We consider the well-studied problem of finding a spanning tree with minimum average distance between vertex pairs (called a MAD tree). This is a classic network design problem whi…
Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density
Matthias Bentert, Tom-Lukas Breitkopf, Vincent Froese +2
We study -Bounded-Density Edge Deletion (-BDED), where given an undirected graph , the task is to remove as few edges as possible to obtain a graph where no subgraph…
There and Back Again: On Applying Data Reduction Rules by Undoing Others
Aleksander Figiel, Vincent Froese, André Nichterlein +1
Data reduction rules are an established method in the algorithmic toolbox for tackling computationally challenging problems. A data reduction rule is a polynomial-time algorithm th…
Disentangling the Computational Complexity of Network Untangling
Vincent Froese, Pascal Kunz, Philipp Zschoche
We study the network untangling problem introduced by Rozenshtein, Tatti, and Gionis [DMKD 2021], which is a variant of Vertex Cover on temporal graphs -- graphs whose edge set cha…
Modification-Fair Cluster Editing
Vincent Froese, Leon Kellerhals, Rolf Niedermeier
The classic Cluster Editing problem (also known as Correlation Clustering) asks to transform a given graph into a disjoint union of cliques (clusters) by a small number of edge mod…
The Complexity of Binary Matrix Completion Under Diameter Constraints
Tomohiro Koana, Vincent Froese, Rolf Niedermeier
We thoroughly study a novel but basic combinatorial matrix completion problem: Given a binary incomplete matrix, fill in the missing entries so that every pair of rows in the resul…
An Average-Compress Algorithm for the Sample Mean Problem under Dynamic Time Warping
Brijnesh Jain, Vincent Froese, David Schultz
Computing a sample mean of time series under dynamic time warping (DTW) is NP-hard. Consequently, there is an ongoing research effort to devise efficient heuristics. The majority o…
Good Things Come to Those Who Swap Objects on Paths
Matthias Bentert, Jiehua Chen, Vincent Froese +1
We study a simple exchange market, introduced by Gourvés, Lesca and Wilczynski (IJCAI-17), where every agent initially holds a single object. The agents have preferences over the o…
Fast Exact Dynamic Time Warping on Run-Length Encoded Time Series
Vincent Froese, Brijnesh Jain, Maciej Rymar +1
Dynamic Time Warping (DTW) is a well-known similarity measure for time series. The standard dynamic programming approach to compute the DTW distance of two length- time series,…
Exact Mean Computation in Dynamic Time Warping Spaces
Markus Brill, Till Fluschnik, Vincent Froese +3
Dynamic time warping constitutes a major tool for analyzing time series. In particular, computing a mean series of a given sample of series in dynamic time warping spaces (by minim…
The Complexity of Finding Effectors
Laurent Bulteau, Stefan Fafianie, Vincent Froese +2
The NP-hard EFFECTORS problem on directed graphs is motivated by applications in network mining, particularly concerning the analysis of probabilistic information-propagation proce…
Triangle counting in dynamic graph streams
Laurent Bulteau, Vincent Froese, Konstantin Kutzkov +1
Estimating the number of triangles in graph streams using a limited amount of memory has become a popular topic in the last decade. Different variations of the problem have been st…