30 citations · 100 across the 41 of their papers we have counts for
14 papers · 1 filter
The Influence of Agent Models on the Complexity of Bus Routing
Eva Deltl, Christian Komusiewicz, Jurek Rostalsky +2
In bus routing, the task is to plan a bus route in a network with several agents, each of whom wants to travel from a starting point to a destination. A bus route should account fo…
On the Hardness of Finding Temporally Connected Subgraphs of Any Size
Arnaud Casteigts, Christian Komusiewicz, Nils Morawietz
Temporal graphs are graphs whose edges are present only at certain points in time. Reachability in these graphs is defined via temporal paths, in which edges are traversed in incre…
A Parameterized-Complexity Framework for Finding Local Optima
Robert Ganian, Hung P. Hoang, Christian Komusiewicz +1
Local search is a fundamental optimization technique that is both widely used in practice and deeply studied in theory, yet its computational complexity remains poorly understood.…
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…
Parameterized Local Search for Max -Cut
Jaroslav Garvardt, Niels Grüttemeier, Christian Komusiewicz +1
In the NP-hard Max -Cut problem, one is given an undirected edge-weighted graph and aims to color the vertices of with colors such that the total weight of edges wit…
Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study
Christian Komusiewicz, Jannik Schestag
In the NP-hard Optimizing PD with Dependencies (PDD) problem, the input consists of a phylogenetic tree over a set of taxa , a food-web that describes the prey-predator rela…
Parameterized String Equations
Laurent Bulteau, Michael R. Fellows, Christian Komusiewicz +1
We study systems of String Equations where block variables need to be assigned strings so that their concatenation gives a specified target string. We investigate this problem unde…
Graph Motif Problems Parameterized by Dual
Guillaume Fertin, Christian Komusiewicz
Let be a vertex-colored graph, where is the set of colors used to color . The Graph Motif (or GM) problem takes as input , a multiset of colors built from $…
Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
Iyad Kanj, Christian Komusiewicz, Manuel Sorge +1
A fundamental graph problem is to recognize whether the vertex set of a graph can be bipartitioned into sets and such that and satisfy properties an…
The Maximum Colorful Arborescence problem parameterized by the structure of its color hierarchy graph
Guillaume Fertin, Julien Fradin, Christian Komusiewicz
Let G=(V,A) be a vertex-colored arc-weighted directed acyclic graph (DAG) rooted in some vertex r, and let H be its color hierarchy graph, defined as follows: V(H) is the color set…
When can Graph Hyperbolicity be computed in Linear Time?
Till Fluschnik, Christian Komusiewicz, George B. Mertzios +3
Hyperbolicity measures, in terms of (distance) metrics, how close a given graph is to being a tree. Due to its relevance in modeling real-world networks, hyperbolicity has seen int…
Parameterized Algorithms for Recognizing Monopolar and 2-Subcolorable Graphs
Iyad Kanj, Christian Komusiewicz, Manuel Sorge +1
A graph is a -graph if can be bipartitioned into and such that satisfies property and satisfies property . The $(Π_{A},Π_{B})…
Assessing the Computational Complexity of Multi-Layer Subgraph Detection
Robert Bredereck, Christian Komusiewicz, Stefan Kratsch +3
Multi-layer graphs consist of several graphs (layers) over the same vertex set. They are motivated by real-world problems where entities (vertices) are associated via multiple type…
On Structural Parameterizations for the 2-Club Problem
Sepp Hartung, Christian Komusiewicz, André Nichterlein +1
The NP-hard 2-Club problem is, given an undirected graph G=(V,E) and l\in N, to decide whether there is a vertex set S\subseteq V of size at least l such that the induced subgraph…