7 citations · 8 across the 3 of their papers we have counts for
8 papers · 1 filter
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…
Recent Advances in Practical Data Reduction
Faisal Abu-Khzam, Sebastian Lamm, Matthias Mnich +3
Over the last two decades, significant advances have been made in the design and analysis of fixed-parameter algorithms for a wide variety of graph-theoretic problems. This has res…
Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations
Alexander Gellner, Sebastian Lamm, Christian Schulz +2
Given a vertex-weighted graph, the maximum weight independent set problem asks for a pair-wise non-adjacent set of vertices such that the sum of their weights is maximum. The branc…
Recent Advances in Scalable Network Generation
Manuel Penschuck, Ulrik Brandes, Michael Hamann +5
Random graph models are frequently used as a controllable and versatile data source for experimental campaigns in various research fields. Generating such data-sets at scale is a n…
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…
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…