157 citations · 421 across the 63 of their papers we have counts for
6 papers · 1 filter
Scalable Graph Algorithms
Christian Schulz
Processing large complex networks recently attracted considerable interest. Complex graphs are useful in a wide range of applications from technological networks to biological syst…
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…
Shared-Memory Branch-and-Reduce for Multiterminal Cuts
Monika Henzinger, Alexander Noe, Christian Schulz
We introduce the fastest known exact algorithm~for~the multiterminal cut problem with k terminals. In particular, we engineer existing as well as new data reduction rules. We use t…
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…
Finding Optimal Longest Paths by Dynamic Programming in Parallel
Kai Fieger, Tomas Balyo, Christian Schulz +1
We propose an exact algorithm for solving the longest simple path problem between two given vertices in undirected weighted graphs. By using graph partitioning and dynamic programm…
Fully Dynamic Single-Source Reachability in Practice: An Experimental Study
Kathrin Hanauer, Monika Henzinger, Christian Schulz
Given a directed graph and a source vertex, the fully dynamic single-source reachability problem is to maintain the set of vertices that are reachable from the given vertex, subjec…