Parameterized Algorithms for Maximum Cut with Connectivity Constraints

Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi +1

We study two variants of \textsc{Maximum Cut}, which we call \textsc{Connected Maximum Cut} and \textsc{Maximum Minimal Cut}, in this paper. In these problems, given an unweighted…