Mathematics – Metric Geometry
Scientific paper
2010-04-03
Mathematics
Metric Geometry
Scientific paper
An extension $(V,d)$ of a metric space $(S,\mu)$ is a metric space with $S \subseteq V$ and $d|_S = \mu$, and is said to be tight if there is no other extension $(V,d')$ of $(S,\mu)$ with $d' \leq d$. 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.
Hirai Hiroshi
Koichi Shungo
No associations
LandOfFree
On tight spans and tropical polytopes for directed distances does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On tight spans and tropical polytopes for directed distances, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On tight spans and tropical polytopes for directed distances will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-198542