We changed our privacy policy. Read more.

Theorem 1. There is an $O(n\log n)$-time algorithm for the problem in the post. Proof. We first state two utility lemmas, for an arbitrary edge-weighted graph $G$. We postpone their proofs, which are standard, to the end. Here is the first lemma. Most likely this is already in the Monma and Suri paper. Given any bipartition $(C_1, C_2)$ of $G$, let $W(C_1, ...

Only top voted, non community-wiki answers of a minimum length are eligible