96 citations · 376 across the 69 of their papers we have counts for
5 papers · 2 filters
Balanced Crown Decomposition for Connectivity Constraints
Katrin Casel, Tobias Friedrich, Davis Issac +2
We introduce the balanced crown decomposition that captures the structure imposed on graphs by their connected induced subgraphs of a given size. Such subgraphs are a popular model…
Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic Geometry
Thomas Bläsius, Tobias Friedrich, Maximilian Katzmann
Finding a minimum vertex cover in a network is a fundamental NP-complete graph problem. One way to deal with its computational hardness, is to trade the qualitative performance of…
Efficiently Computing Maximum Flows in Scale-Free Networks
Thomas Bläsius, Tobias Friedrich, Christopher Weyand
We study the maximum-flow/minimum-cut problem on scale-free networks, i.e., graphs whose degree distribution follows a power-law. We propose a simple algorithm that capitalizes on…
A Strategic Routing Framework and Algorithms for Computing Alternative Paths
Thomas Bläsius, Maximilian Böther, Philipp Fischbeck +9
Traditional navigation services find the fastest route for a single driver. Though always using the fastest route seems desirable for every individual, selfish behavior can have un…
Shortest Distances as Enumeration Problem
Katrin Casel, Tobias Friedrich, Stefan Neubert +1
We investigate the single source shortest distance (SSSD) and all pairs shortest distance (APSD) problems as enumeration problems (on unweighted and integer weighted graphs), meani…