G-94-29
Labeling Algortihm for Minimum Sum of Diameters Partitioning of Graphs
, , and BibTeX reference
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.
Published July 1994 , 12 pages