4 citations · 10 across the 13 of their papers we have counts for
13 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…
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…
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…
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…
Witty: An Efficient Solver for Computing Minimum-Size Decision Trees
Luca Pascal Staus, Christian Komusiewicz, Frank Sommer +1
Decision trees are a classic model for summarizing and classifying data. To enhance interpretability and generalization properties, it has been proposed to favor small decision tre…
On the Complexity of Community-aware Network Sparsification
Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz +1
Network sparsification is the task of reducing the number of edges of a given graph while preserving some crucial graph property. In community-aware network sparsification, the pre…
Efficient Branch-and-Bound Algorithms for Finding Triangle-Constrained 2-Clubs
Niels Grüttemeier, Philipp Heinrich Keßler, Christian Komusiewicz +1
In the Vertex Triangle 2-Club problem, we are given an undirected graph and aim to find a maximum-vertex subgraph of that has diameter at most 2 and in which every vertex i…
The Parameterized Complexity of s-Club with Triangle and Seed Constraints
Jaroslav Garvardt, Christian Komusiewicz, Frank Sommer
The s-Club problem asks, for a given undirected graph , whether contains a vertex set of size at least such that , the subgraph of induced by , has diam…
Covering Many (or Few) Edges with k Vertices in Sparse Graphs
Tomohiro Koana, Christian Komusiewicz, André Nichterlein +1
We study the following two fixed-cardinality optimization problems (a maximization and a minimization variant). For a fixed between zero and one we are given a graph and two nu…
Preventing Small -Cuts by Protecting Edges
Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz +1
We introduce and study Weighted Min -Cut Prevention, where we are given a graph with vertices and and an edge cost function and the aim is to choose an edg…
Destroying Multicolored Paths and Cycles in Edge-Colored Graphs
Nils Jakob Eckstein, Niels Grüttemeier, Christian Komusiewicz +1
We study the computational complexity of -Colored Deletion and -Colored Deletion. In these problems, one is given a -edge-colored graph and wants to dest…
Essentially Tight Kernels for (Weakly) Closed Graphs
Tomohiro Koana, Christian Komusiewicz, Frank Sommer
We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closu…
Destroying Bicolored s by Deleting Few Edges
Niels Grüttemeier, Christian Komusiewicz, Jannik Schestag +1
We introduce and study the Bicolored Deletion problem defined as follows. The input is a graph where the edge set is partitioned into a set of red edges a…