4 papers
On the Parameterized Complexity of Bounded-Density Vertex Deletion
Jakob Raupach, Tom-Lukas Breitkopf, Anton Herrmann +1
We explore the parameterized complexity of Bounded Density Vertex Deletion (BDVD): given a graph , an integer budget , and a target density , the task is to determine…
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 subgrap…
Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
Anton Herrmann, Christian Komusiewicz, Nils Morawietz +1
A temporal graph is a finite sequence of graphs, called snapshots, over the same vertex set. Many temporal graph problems turn out to be much more difficult than their static count…