19 citations · 118 across the 26 of their papers we have counts for
12 papers · 1 filter
Parameterized Algorithms for Matrix Completion With Radius Constraints
Tomohiro Koana, Vincent Froese, Rolf Niedermeier
Considering matrices with missing entries, we study NP-hard matrix completion problems where the resulting completed matrix shall have limited (local) radius. In the pure radius ve…
Faster Binary Mean Computation Under Dynamic Time Warping
Nathan Schaar, Vincent Froese, Rolf Niedermeier
Many consensus string problems are based on Hamming distance. We replace Hamming distance by the more flexible (e.g., easily coping with different input string lengths) dynamic tim…
Persistent Graphs and Cyclic Polytope Triangulations
Vincent Froese, Malte Renken
We prove a bijection between the triangulations of the 3-dimensional cyclic polytope C(n+2, 3) and persistent graphs with n vertices. We show that under this bijection the Stasheff…
Tight Hardness Results for Consensus Problems on Circular Strings and Time Series
Laurent Bulteau, Vincent Froese, Rolf Niedermeier
Consensus problems for strings and sequences appear in numerous application contexts, ranging from bioinformatics over data mining to machine learning. Closing some gaps in the lit…
Computational Complexity Aspects of Point Visibility Graphs
Anne-Sophie Himmel, Clemens Hoffmann, Pascal Kunz +2
A point visibility graph is a graph induced by a set of points in the plane where the vertices of the graph represent the points in the point set and two vertices are adjacent if a…
A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed Graphs
Robert Bredereck, Vincent Froese, Marcel Koseler +3
There has been intensive work on the parameterized complexity of the typically NP-hard task to edit undirected graphs into graphs fulfilling certain given vertex degree constraints…
Exploiting Hidden Structure in Selecting Dimensions that Distinguish Vectors
Vincent Froese, René van Bevern, Rolf Niedermeier +1
The NP-hard Distinct Vectors problem asks to delete as many columns as possible from a matrix such that all rows in the resulting matrix are still pairwise distinct. Our main resul…
Co-Clustering Under the Maximum Norm
Laurent Bulteau, Vincent Froese, Sepp Hartung +1
Co-clustering, that is, partitioning a numerical matrix into homogeneous submatrices, has many applications ranging from bioinformatics to election analysis. Many interesting varia…
Parameterizing edge modification problems above lower bounds
René van Bevern, Vincent Froese, Christian Komusiewicz
We study the parameterized complexity of a variant of the -free Editing problem: Given a graph and a natural number , is it possible to modify at most edges in so…
Win-Win Kernelization for Degree Sequence Completion Problems
Vincent Froese, André Nichterlein, Rolf Niedermeier
We study provably effective and efficient data reduction for a class of NP-hard graph modification problems based on vertex degree properties. We show fixed-parameter tractability…
Network-Based Vertex Dissolution
René van Bevern, Robert Bredereck, Jiehua Chen +3
We introduce a graph-theoretic vertex dissolution model that applies to a number of redistribution scenarios such as gerrymandering in political districting or work balancing in an…
Partitioning Perfect Graphs into Stars
René van Bevern, Robert Bredereck, Laurent Bulteau +4
The partition of graphs into "nice" subgraphs is a central algorithmic problem with strong ties to matching theory. We study the partitioning of undirected graphs into same-size st…