Optimal realizations of two-dimensional, totally-decomposable metrics

DOI10.1016/j.disc.2015.02.008zbMath1310.05111arXiv1108.0290OpenAlexW2054108637MaRDI QIDQ2342613

Alice Lesser, Sven Herrmann, Taoyang Wu, Jack H. Koolen, Vincent L. Moulton

Publication date: 29 April 2015

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1108.0290

zbMATH Keywords

Buneman complexoptimal realizationstight-spanManhattan network problemtotally-decomposable metrics

Mathematics Subject Classification ID

Small world graphs, complex networks (graph-theoretic aspects) (05C82) Paths and cycles (05C38) Distance in graphs (05C12) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Signed and weighted graphs (05C22)

Related Items

Searching for realizations of finite metric spaces in tight spans

Cites Work

• Unnamed Item
• Injective optimal realizations of finite metric spaces
• Minimum Manhattan network is NP-complete
• An explicit computation of the injective hull of certain finite metric spaces in terms of their associated Buneman complex
• The metric cutpoint partition problem
• On optimal embeddings of metrics in graphs
• On the structure of the tight-span of a totally split-decomposable metric
• The metric bridge partition problem: Partitioning of a metric space into two subspaces linked by an edge in any optimal realization
• Tight spans of distances and the dual fractionality of undirected multiflow problems
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• On optimal realizations of finite metric spaces by graphs
• A canonical decomposition theory for metrics on a finite set
• A comparison between two distinct continuous models in projective cluster theory: The median and the tight-span construction
• Metrics with finite sets of primitive extensions
• Some variations on a theme by Buneman
• Searching for realizations of finite metric spaces in tight spans
• Graphs of some CAT(0) complexes
• Concerning the relationship between realizations and tight spans of finite metrics
• Six theorems about injective metric spaces
• The Complexity of Metric Realization
• Lectures on Polytopes
• Distance matrix of a graph and its realizability
• Totally split-decomposable metrics of combinatorial dimension two