An algorithm for computing cutpoints in finite metric spaces

DOI10.1007/S00357-010-9055-7MaRDI QIDQ263276zbMATHOpenAlexFDO

Authors Andreas Spillner, Katharina T. Huber, Andreas W. M. Dress, Jack H. Koolen, Vincent Moulton

Publication date 4 April 2016

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

Full work available at URL https://doi.org/10.1007/s00357-010-9055-7

zbMATH Keywords

decompositionblockmetriccutpointrealizationtight span

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Metric spaces, metrizability (54E35)

Recommendations

• An Algorithm for Computing Virtual Cut Points in Finite Metric Spaces
• The metric cutpoint partition problem
• Searching for realizations of finite metric spaces in tight spans
• Obtaining splits from cut sets of tight spans
• Trimming of metric spaces and the tight span

Cites work

• scientific article; zbMATH DE number 854567 (Why is no real title available?)
• scientific article; zbMATH DE number 3270498 (Why is no real title available?)
• A canonical decomposition theory for metrics on a finite set
• A structured family of clustering and tree construction methods
• An Algorithm for Computing Virtual Cut Points in Finite Metric Spaces
• Block realizations of finite metrics and the tight-span construction. I: The embedding theorem
• Compatible decompositions and block realizations of finite metrics
• Cut points in metric spaces
• Distance realization problems with applications to internet tomography
• Geometry of cuts and metrics
• Introduction to algorithms
• On optimal embeddings of metrics in graphs
• Quelques problèmes concernant les espaces métriques non-séparables
• Simple algorithms for the on-line multidimensional dictionary and related problems
• Six theorems about injective metric spaces
• The metric bridge partition problem: Partitioning of a metric space into two subspaces linked by an edge in any optimal realization
• The metric cutpoint partition problem
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces

Cited in

(15)

• Trees, tight-spans and point configurations
• Searching for realizations of finite metric spaces in tight spans
• An Algorithm for Computing Virtual Cut Points in Finite Metric Spaces
• A polynomial time computable metric between points sets
• Recognizing and realizing cactus metrics
• Injective optimal realizations of finite metric spaces
• Obtaining splits from cut sets of tight spans
• The metric cutpoint partition problem
• Distance spectra of graphs: a survey
• An algorithm for the construction of the tight span of finite subsets of the Manhattan plane
• scientific article; zbMATH DE number 1440917 (Why is no real title available?)
• Algorithm 825
• Cut points in metric spaces
• Computing the blocks of a quasi-median graph
• Optimal realizations and the block decomposition of a finite metric space

This page was built for publication: An algorithm for computing cutpoints in finite metric spaces

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