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

G-2005-67

The Metric Bridge Partition Problem

et

Let G = (V,E,w) be a graph with vertex and edge sets V and E, respectively, and w : E IR+ a function which assigns a positive weigth or length to each edge of G. G is called a realization of a finite metric space (M, d), with M = {1, ..., n} if and only if {1, ..., n} V and d(i, j) is equal to the length of the shortest chain linking i and j in G i, j = 1, ..., n. A realization G of (M, d), is said optimal if the sum of its weights is minimal among all the realizations of (M, d). Consider a partition of M into two nonempty subsets K and L, and let e be an edge in a realization G of (M, d); we say that e is a bridge linking K with L if e belongs to all chains in G linking a vertex of K with a vertex of L. The Metric Bridge Partition Problem is to determine if the elements of a finite metric space (M, d) can be partitioned into two nonempty subsets K and L such that all optimal realizations of (M, d) contain a bridge linking K with L. We prove in this paper that this problem is polynomially solvable. We also describe an algorithm that constructs an optimal realization of (M, d) from optimal realizations of (K, d|K) and (L, d|L).

, 19 pages