On tight spans for directed distances

DOI10.1007/S00026-012-0146-5zbMATH Open1271.54064arXiv1004.0415OpenAlexW2075413677MaRDI QIDQ1928578FDOQ1928578

Hiroshi Hirai, Shungo Koichi

Publication date: 3 January 2013

Published in: Annals of Combinatorics (Search for Journal in Brave)

Abstract: An extension $(V,d)$ of a metric space $(S,mu)$ is a metric space with $SsubseteqV$ and $d{|}_S=mu$, and is said to be tight if there is no other extension $(V,d^{\prime })$ of $(S,mu)$ with $d^{\prime }leqd$. Isbell and Dress independently found that every tight extension is isometrically embedded into a certain metrized polyhedral complex associated with $(S,mu)$, called the tight span. This paper develops an analogous theory for directed metrics, which are "not necessarily symmetric" distance functions satisfying the triangle inequality. We introduce a directed version of the tight span and show that it has such a universal embedding property for tight extensions. Also we newly introduce another natural class of extensions, called cyclically tight extensions, and show that (a fiber of) the tropical polytope, introduced by Develin and Sturmfels, has a universal embedding property for cyclically tight extensions. As an application, we prove the following directed version of tree metric theorem: directed metric $mu$ is a directed tree metric if and only if the tropical rank of $-mu$ is at most two. Also we describe how tight spans and tropical polytopes are applied to the study in multicommodity flows in directed networks.

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

zbMATH Keywords

tropical polytopesmetricsmulticommodity flowstight spans

Mathematics Subject Classification ID

Distance in graphs (05C12) Extensions of spaces (compactifications, supercompactifications, completions, etc.) (54D35) Topological spaces with richer structures (54E99)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Trees, tight extensions of metric spaces, and the cohomological dimension of certain groups: A note on combinatorial properties of metric spaces
• A note on the metric properties of trees
• A note on the tree realizability of a distance matrix
• Tropical convexity
• A canonical decomposition theory for metrics on a finite set
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Six theorems about injective metric spaces
• Basic Phylogenetic Combinatorics
• State of the Art—Location on Networks: A Survey. Part I: The p-Center and p-Median Problems
• Directed metrics and directed graph partitioning problems
• Classification of six-point metrics
• The distance matrix of a graph and its tree realization
• Trees, tight-spans and point configurations
• Combinatorial approaches to multiflow problems
• Tight spans of distances and the dual fractionality of undirected multiflow problems
• Metrics with finite sets of primitive extensions
• Minimum 0-extensions of graph metrics
• Characterization of the distance between subtrees of a tree by the associated tight span
• A geometric study of the split decomposition
• Folder Complexes and Multiflow Combinatorial Dualities
• Generosity Helps or an 11-Competitive Algorithm for Three Servers
• A fast algorithm for finding a maximum free multiflow in an inner Eulerian network and some generalizatons
• On duality and fractionality of multicommodity flows in directed networks
• Gradient flows in asymmetric metric spaces
• A characterization of minimizable metrics in the multifacility location problem
• The directed circular arrangement problem

Cited In (10)

• Completeness and injectivity
• Isbell conjugacy and the reflexive completion
• Endpoints in \(T_0\)-quasimetric spaces. II.
• A construction of the \(B\)-completion of a \(T_0\)-quasi-metric space
• Tight spans of distances and the dual fractionality of undirected multiflow problems
• The vector lattice structure on the Isbell-convex hull of an asymmetrically normed real vector space
• A generalized inverse for graphs with absorption
• On duality and fractionality of multicommodity flows in directed networks
• Trees, tight-spans and point configurations
• Extremal Distances in Directed Graphs: Tight Spanners and Near-Optimal Approximation Algorithms

Recommendations

• Title not available (Why is that?) 👍 👎
• \(T\)-theory: An overview 👍 👎
• On the existence of shortest directed networks 👍 👎
• Trees, tight-spans and point configurations 👍 👎
• Injective optimal realizations of finite metric spaces 👍 👎
• The Weak Gap Property in Metric Spaces of Bounded Doubling Dimension 👍 👎
• Characterization of the distance between subtrees of a tree by the associated tight span 👍 👎
• On duality and fractionality of multicommodity flows in directed networks 👍 👎
• Searching for realizations of finite metric spaces in tight spans 👍 👎
• Optimal realizations of two-dimensional, totally-decomposable metrics 👍 👎

This page was built for publication: On tight spans for directed distances

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