Shared-Memory Branch-and-Reduce for Multiterminal Cuts

Monika Henzinger, Alexander Noe, Christian Schulz

Veröffentlichungen: Beitrag in BuchBeitrag in KonferenzbandPeer Reviewed

Abstract

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 the rules within a branch-and-reduce framework and to boost the performance of an ILP formulation. Our algorithms achieve improvements in running time of up to multiple orders of magnitudes over the ILP formulation without data reductions, which has been the de facto standard used by practitioners. This allows us to solve instances to optimality that are significantly larger than was previously possible.

OriginalspracheEnglisch
Titel2020 Proceedings of the Symposium on Algorithm Engineering and Experiments, ALENEX 2020
Redakteure*innenGuy Blelloch, Irene Finocchi
Seiten42-55
Seitenumfang14
ISBN (elektronisch)9781611976007
DOIs
PublikationsstatusVeröffentlicht - 5 Jan. 2020
VeranstaltungALENEX 2020 - Salt Lake City, Utah, USA / Vereinigte Staaten
Dauer: 5 Jan. 20207 Jan. 2020
https://www.siam.org/conferences/cm/conference/soda20

Konferenz

KonferenzALENEX 2020
Land/GebietUSA / Vereinigte Staaten
OrtSalt Lake City, Utah
Zeitraum5/01/207/01/20
Internetadresse

ÖFOS 2012

  • 102031 Theoretische Informatik

Zitationsweisen