Showing cs.DMShow all
2 papers · 1 filter
cs.DM2019
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…
cs.DM2018
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…