-
Article
Cluster Editing for Multi-Layer and Temporal Graphs
Motivated by the recent rapid growth of research for algorithms to cluster multi-layer and temporal graphs, we study extensions of the classical Cluster Editing problem. In Multi-Layer Cluster Editing we receive ...
-
Chapter and Conference Paper
The Complexity of Cluster Vertex Splitting and Company
Clustering a graph when the clusters can overlap can be seen from three different angles: We may look for cliques that cover the edges of the graph with bounded overlap, we may look to add or delete few edges ...
-
Article
Open AccessThe Complexity of Routing Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk ...
-
Chapter and Conference Paper
Planarizing Graphs and Their Drawings by Vertex Splitting
The splitting number of a graph \(G=(V,E)\) G = ...
-
Article
Packing Directed Cycles Quarter- and Half-Integrally
The celebrated Erdős-Pósa theorem states that every undirected graph that does not admit a family of k vertex-disjoint cycles contains a feedback vertex set (a set of vertices hitting all cycles in the graph) of ...
-
Chapter and Conference Paper
Constant Congestion Brambles in Directed Graphs
The Directed Grid Theorem, stating that there is a function f such that a directed graph of directed treewidth at least f(k) contains a directed grid of size at least k as a butterfly minor, after being a conject...
-
Chapter and Conference Paper
On (Coalitional) Exchange-Stable Matching
We study , which Alcalde [Economic Design, 1995] introduced as an alternative solution concept for matching markets involving property rights, such as assigning persons to ...
-
Article
Efficient algorithms for measuring the funnel-likeness of DAGs
We propose funnels as a new natural subclass of DAGs. Intuitively, a DAG is a funnel if every source-sink path can be uniquely identified by one of its arcs. Funnels are an analogue to trees for directed graph...
-
Article
The Minimum Feasible Tileset Problem
We introduce and study the Minimum Feasible Tileset problem: given a set of symbols and subsets of these symbols (scenarios), find a smallest possible number of pairs of symbols (tiles) such that each scenario ca...
-
Chapter and Conference Paper
Your Rugby Mates Don’t Need to Know Your Colleagues: Triadic Closure with Edge Colors
Given an undirected graph \(G=(V,E)\) the NP-hard Strong Triadic Closure (STC) problem asks for a labeling of the edg...
-
Chapter and Conference Paper
Efficient Algorithms for Measuring the Funnel-Likeness of DAGs
Funnels are a new natural subclass of DAGs. Intuitively, a DAG is a funnel if every source-sink path can be uniquely identified by one of its arcs. Funnels are an analog to trees for directed graphs that is mo...
-
Chapter and Conference Paper
The Parameterized Complexity of Centrality Improvement in Networks
The centrality of a vertex v in a network intuitively captures how important v is for communication in the network. The task of improving the centrality of a vertex has many applications, as a higher centrality o...
-
Article
On Kernelization and Approximation for the Vector Connectivity Problem
In the Vector Connectivity problem we are given an undirected graph \(G=(V,E)\) ...
-
Article
Adapting the Bron–Kerbosch algorithm for enumerating maximal cliques in temporal graphs
Dynamics of interactions play an increasingly important role in the analysis of complex networks. A modeling framework to capture this is temporal graphs which consist of a set of vertices (entities in the net...
-
Chapter and Conference Paper
The Complexity of Routing with Few Collisions
We study the computational complexity of routing multiple objects through a network in such a way that only few collisions occur: Given a graph G with two distinct terminal vertices and two positive integers p an...
-
Chapter and Conference Paper
Assessing the Computational Complexity of Multi-layer Subgraph Detection
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 types of relationships (edges in ...
-
Chapter and Conference Paper
Twins in Subdivision Drawings of Hypergraphs
Visualizing hypergraphs, systems of subsets of some universe, has continuously attracted research interest in the last decades. We study a natural kind of hypergraph visualization called subdivision drawings. Din...
-
Article
On the Parameterized Complexity of Computing Balanced Partitions in Graphs
A balanced partition is a clustering of a graph into a given number of equal-sized parts. For instance, the Bisection problem asks to remove at most k edges in order to partition the vertices into two equal-sized...
-
Chapter and Conference Paper
Finding Connected Subgraphs of Fixed Minimum Density: Implementation and Experiments
We consider the following problem. Given a graph and a rational number \(\mu \) ,
-
Chapter and Conference Paper
The Minimum Feasible Tileset Problem
We consider the Minimum Feasible Tileset problem: Given a set of symbols and subsets of these symbols (scenarios), find a smallest possible number of pairs of symbols (tiles) such that each scenario can be formed...
