10 papers
Exact and Approximate Algorithms for Polytree Learning
Juha Harviainen, Frank Sommer, Manuel Sorge
Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of variables as a directed forest and are motivated by their more…
Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
Niels Grüttemeier, Nils Morawietz, Frank Sommer
Parameterized local search combines classic local search heuristics with the paradigm of parameterized algorithmics. While most local search algorithms aim to improve given solutio…
The Parameter Report: An Orientation Guide for Data-Driven Parameterization
Christian Komusiewicz, Nils Morawietz, Frank Sommer +1
A strength of parameterized algorithmics is that each problem can be parameterized by an essentially inexhaustible set of parameters. Usually, the choice of the considered paramete…
Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii
Thomas Depian, Frank Sommer
For a fixed graph class , the goal of -Modification is to transform an input graph into a graph using at most modifications. Vertex and edge deletions are com…
Improving Decision Trees through the Lens of Parameterized Local Search
Juha Harviainen, Frank Sommer, Manuel Sorge
Algorithms for learning decision trees often include heuristic local-search operations such as (1) adjusting the threshold of a cut or (2) also exchanging the feature of that cut.…
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…