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…