The metric cutpoint partition problem

DOI10.1007/s00357-008-9016-6zbMath1275.05056OpenAlexW2133276644MaRDI QIDQ734378

Alain Hertz, Sacha C. Varone

Publication date: 13 October 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%2C20091015102807-RJ/varone_metric_cutpoint.pdf

zbMATH Keywords

metric spacespolynomial algorithmbridgecutpointoptimal realizationsmetric cutpoint partition problem

Mathematics Subject Classification ID

Metric spaces, metrizability (54E35) Graph algorithms (graph-theoretic aspects) (05C85) Finite geometry and special incidence structures (51E99)

Related Items

Injective optimal realizations of finite metric spaces, Cut points in metric spaces, Distance spectra of graphs: a survey, Searching for realizations of finite metric spaces in tight spans, Optimal realizations and the block decomposition of a finite metric space, Recognizing and realizing cactus metrics, Optimal realizations of two-dimensional, totally-decomposable metrics, An algorithm for computing cutpoints in finite metric spaces

Cites Work

• Unnamed Item
• Unnamed Item
• On optimal embeddings of metrics in graphs
• The metric bridge partition problem: Partitioning of a metric space into two subspaces linked by an edge in any optimal realization
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• Free trees and bidirectional trees as representations of psychological distance
• Distance realization problems with applications to internet tomography
• The Similarity Metric
• An Algorithm for Computing Virtual Cut Points in Finite Metric Spaces
• The Complexity of Metric Realization
• Distance matrix of a graph and its realizability