Back

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.

, 12 pages