On the existence of shortest directed networks

Details On the existence of shortest directed networks On the existence of shortest directed networks

2008-10-09

arxiv.org/abs/0810.1638v1

J. Combin. Math. Combin. Comput. 33 (2000), 97--102

Mathematics

Metric Geometry

6 pages. An old paper from 2000

Scientific paper

A directed network connecting a set A to a set B is a digraph containing an a-b path for each a in A and b in B. Vertices in the directed network not in A or B are called Steiner points. We show that in a finitely compact metric space in which geodesics exist, any two finite sets A and B are connected by a shortest directed network. We also bound the number of Steiner points by a function of the sizes of A and B. Previously, such an existence result was known only for the Euclidean plane [M. Alfaro, Pacific J. Math. 167 (1995) 201-214]. The main difficulty is that, unlike the undirected case (Steiner minimal trees), the underlying graphs need not be acyclic. Existence in the undirected case was first shown by E. J. Cockayne [Canad. Math. Bull. 10 (1967) 431-450].

Affiliated with

Also associated with

No associations

Rating

On the existence of shortest directed networks 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 the existence of shortest directed networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the existence of shortest directed networks will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-460883