The metric cutpoint partition problem

DOI10.1007/s00357-008-9016-6zbMath1275.05056MaRDI 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 spaces; polynomial algorithm; bridge; cutpoint; optimal realizations; metric cutpoint partition problem

Mathematics Subject Classification ID

54E35: Metric spaces, metrizability

05C85: Graph algorithms (graph-theoretic aspects)

51E99: Finite geometry and special incidence structures

Related Items

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

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