An O (mn log n) labeling algorithm is proposed for minimum sum of diameters bipartitioning of the vertex set of a weighted graph (with n vertices and m edges). The diameter of a set of vertices is defined as the largest weight of an edge joining two vertices in that set. This algorithm has, in fact, a lower complexity than a previous one due to Monma and Suri.