G-2006-04
The Metric Cutpoint Partition Problem
et référence BibTeX
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.
Paru en janvier 2006 , 20 pages