10 papers
Parameterized Complexity of Spanner Problems with Independent Weights and Lengths
Marius Bächler, Markus Chimani, Henning Jasper
In this paper, the parameterized complexity of the multiplicative -spanner problem with independent weights and lengths on undirected graphs is considered for the first time. Al…
Designing Capacitated Subnetworks for Shortest Path Routing
Markus Chimani, Max Ilsen
In pursuit of higher energy efficiency in computer networks, one subfield of green traffic engineering aims at reducing the size of a network during times of low traffic, while sti…
No Traffic to Cry: Traffic-Oblivious Link Deactivation for Green Traffic Engineering
Max Ilsen, Daniel Otten, Nils Aschenbruck +1
As internet traffic grows, the underlying infrastructure consumes increasing amounts of energy. During off-peak hours, large parts of the networks remain underutilized, presenting…
Simple Approximations for General Spanner Problems
Fritz Bökler, Markus Chimani, Henning Jasper
Consider a graph with n nodes and m edges, independent edge weights and lengths, and arbitrary distance demands for node pairs. The spanner problem asks for a minimum-weight subgra…
Two-edge-connected (not necessarily spanning) subgraphs and polyhedra
Justus Bruckamp, Markus Chimani, Martina Juhnke
Given a graph , we study the -edge-connected subgraph polytope , which is given by the convex hull of the incidence vectors of all -edge-connected subgr…
A Systematic Approach to Crossing Numbers of Cartesian Products with Paths
Zayed Asiri, Ryan Burdett, Markus Chimani +3
Determining the crossing numbers of Cartesian products of small graphs with arbitrarily large paths has been an ongoing topic of research since the 1970s. Doing so requires the est…
The Price of Upwardness
Patrizio Angelini, Therese Biedl, Markus Chimani +8
Not every directed acyclic graph (DAG) whose underlying undirected graph is planar admits an upward planar drawing. We are interested in pushing the notion of upward drawings beyon…
Crossing Numbers of Beyond Planar Graphs Re-revisited: A Framework Approach
Markus Chimani, Torben Donzelmann, Nick Kloster +3
Beyond planarity concepts (prominent examples include k-planarity or fan-planarity) apply certain restrictions on the allowed patterns of crossings in drawings. It is natural to as…
Exact Minimum Weight Spanners via Column Generation
Fritz Bökler, Markus Chimani, Henning Jasper +1
Given a weighted graph , a minimum weight -spanner is a least-weight subgraph that preserves minimum distances between all node pairs up to a factor of . Th…
On the Dominant of the Multicut Polytope
Markus Chimani, Martina Juhnke-Kubitzke, Alexander Nover
Given a graph and a set of terminal pairs, the minimum multicut problem asks for a minimum edge set such that there is no -$t…