1 citations · 1 across the 3 of their papers we have counts for
5 papers
On Sparse Hitting Sets: from Fair Vertex Cover to Highway Dimension
Johannes Blum, Yann Disser, Andreas Emil Feldmann +2
We consider the Sparse Hitting Set (Sparse-HS) problem, where we are given a set system with two families of subsets of .…
Customizable Hub Labeling: Properties and Algorithms
Johannes Blum, Sabine Storandt
Hub Labeling (HL) is one of the state-of-the-art preprocessing-based techniques for route planning in road networks. It is a special incarnation of distance labeling, and it is wel…
W[1]-Hardness of the k-Center Problem Parameterized by the Skeleton Dimension
Johannes Blum
In the -Center problem, we are given a graph with positive edge weights and an integer and the goal is to select center vertices such that the…
Hierarchy of Transportation Network Parameters and Hardness Results
Johannes Blum
The graph parameters highway dimension and skeleton dimension were introduced to capture the properties of transportation networks. As many important optimization problems like Tra…
Planar Steiner Orientation is NP-complete
Moritz Beck, Johannes Blum, Myroslav Kryven +2
Many applications in graph theory are motivated by routing or flow problems. Among these problems is Steiner Orientation: given a mixed graph G (having directed and undirected edge…