10 citations · 13 across the 7 of their papers we have counts for
6 papers · 1 filter
Pareto Sums of Pareto Sets: Lower Bounds and Algorithms
Daniel Funke, Demian Hespe, Peter Sanders +2
In bi-criteria optimization problems, the goal is typically to compute the set of Pareto-optimal solutions. Many algorithms for these types of problems rely on efficient merging or…
Targeted Branching for the Maximum Independent Set Problem
Demian Hespe, Sebastian Lamm, Christian Schorr
Finding a maximum independent set is a fundamental NP-hard problem that is used in many real-world applications. Given an unweighted graph, this problem asks for a maximum cardinal…
WeGotYouCovered: The Winning Solver from the PACE 2019 Implementation Challenge, Vertex Cover Track
Demian Hespe, Sebastian Lamm, Christian Schulz +1
We present the winning solver of the PACE 2019 Implementation Challenge, Vertex Cover Track. The minimum vertex cover problem is one of a handful of problems for which kernelizatio…
More Hierarchy in Route Planning Using Edge Hierarchies
Demian Hespe, Peter Sanders
A highly successful approach to route planning in networks (particularly road networks) is to identify a hierarchy in the network that allows faster queries after some preprocessin…
Engineering Kernelization for Maximum Cut
Damir Ferizovic, Demian Hespe, Sebastian Lamm +3
Kernelization is a general theoretical framework for preprocessing instances of NP-hard problems into (generally smaller) instances with bounded size, via the repeated application…
Scalable Kernelization for Maximum Independent Sets
Demian Hespe, Christian Schulz, Darren Strash
The most efficient algorithms for finding maximum independent sets in both theory and practice use reduction rules to obtain a much smaller problem instance called a kernel. The ke…