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

G-2006-04

The Metric Cutpoint Partition Problem

et

Let be a graph with vertex and edge sets and , respectively, and a function which assigns a positive weight or length to each edge of . is called a realization of a finite metric space , with if and only if and is equal to the length of the shortest chain linking and in . A realization of , is said optimal if the sum of its weights is minimal among all the realizations of . A cutpoint in a graph is a vertex whose removal strictly increases the number of connected component of . The Metric Cutpoint Partition Problem is to determine if a finite metric space has an optimal realization containing a cutpoint. We prove in this paper that this problem is polynomially solvable. We also describe an algorithm that constructs an optimal realization of from optimal realizations of subspaces that do not contain any cutpoint.

, 20 pages