Groupe d’études et de recherche en analyse des décisions

# Labeling Algortihm for Minimum Sum of Diameters Partitioning of Graphs

## Sylvie Gélinas, Pierre Hansen et Brigitte Jaumard

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