The metric bridge partition problem: Partitioning of a metric space into two subspaces linked by an edge in any optimal realization

DOI10.1007/S00357-007-0011-0MaRDI QIDQ1015445zbMATH OpenOpenAlexFDO

Authors Alain Hertz, Sacha C. Varone

Publication date 8 May 2009

Published in Journal of Classification (Search for Journal in Brave)

Full work available at URL http://doc.rero.ch/lm.php?url=1000%2C43%2C9%2C20091013165829-WT/Varone_metric_bridge.pdf

zbMATH Keywords

metric bridge partition problemoptimal realizationrealization of finite metric space

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Metric spaces, metrizability (54E35) Programming involving graphs or networks (90C35)

Review text

Let \(G=(V,E,w)\) be a graph with vertex and edge sets \(V\) and \(E\), respectively, and \(w:E\rightarrow {\mathbb{R}}^+\) a function which assigns a positive weight to each edge of \(G.\) Then \(G\) is called a realization of a finite metric space \((M,d),\) with \(M=\{1,\ldots,n\}\) if and only if \(\{1,\ldots,n\}\subseteq V\) and \(d(i,j)\) is equal to the length of the shortest chain linking \(i\) and \(j\) in \(G,\) whenever \(i,j\in \{1,\ldots,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)\). 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\). The authors prove that this problem is polynomially solvable. They also describe an algorithm that constructs an optimal realization of \((M,d)\) from optimal realizations of \((K,d_{| K})\) and \((L,d_{| L})\).

Recommendations

• The metric cutpoint partition problem
• Metric space method for constructing splitting partitions of graphs
• scientific article; zbMATH DE number 2062987
• Vertex partitions of metric spaces with finite distance sets
• On dimension partitions in discrete metric spaces
• Extensions of the optimal partition problem for a measure space
• On finding optimal partitions of measurable space
• Optimal Partitioning of a Measurable Space
• The metric properties of partitions of arbitrary sets
• Approximation schemes for metric bisection and partitioning

Cited in

(6)

• Searching for realizations of finite metric spaces in tight spans
• Optimal realizations and the block decomposition of a finite metric space
• Optimal realizations of two-dimensional, totally-decomposable metrics
• An algorithm for computing cutpoints in finite metric spaces
• The metric cutpoint partition problem
• Cut points in metric spaces

This page was built for publication: The metric bridge partition problem: Partitioning of a metric space into two subspaces linked by an edge in any optimal realization

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1015445)