3 papers
cs.DS2026
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…
cs.DS2026
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…
cs.DS2026
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 subgrap…