  We give an improved branch-and-bound solver for the multiterminal cut
problem, based on the recent work of Henzinger et al.. We contribute new,
highly effective data reduction rules to transform the graph into a smaller
equivalent instance. In addition, we present a local search algorithm that can
significantly improve a given solution to the multiterminal cut problem. Our
exact algorithm is able to give exact solutions to more and harder problems
compared to the state-of-the-art algorithm by Henzinger et al.; and give better
solutions for more than two third of the problems that are too large to be
solved to optimality. Additionally, we give an inexact heuristic algorithm that
computes high-quality solutions for very hard instances in reasonable time.
