Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

Median Hulls as Steiner Hulls in Rectilinear and Molecular Sequence Spaces
(Invited presentation)

Hans-J. BandeltContact Information

(5)  Departement of Mathematics, University of Hamburg, Germany
Abstract
The Steiner problem is to find a shortest connection of a finite subset X in a given metric space (M, d). If the space meets some local compactness and connectivity conditions, then a solution, a Steiner minimal tree for X, exists [7]. More generally, considering any graph-theoretic tree T with all nodes of degree < 3 labeled by elements of X (that is, an X-labeled tree), we may ask for a minimal length realization of T in (M, d), that is, for an embedding of the node set of T in M which extends the identity map of X and yields the smallest possible length of the image Steiner tree (relative to the labeled tree T). The embedded unlabeled nodes of T are called Steiner points. A Steiner minimal tree is then that realization which attains minimum length among the (finite) collection of X-labeled trees. Given the subset X, one is interested in restricting the search for Steiner points in the metric space (M, d). Any proper subset of M that is guaranteed to harbor at least one Steiner minimal tree for X is called a Steiner hull for X 7,12. Particular interest attaches to Steiner hulls that are finitely generated in that they are determined by a finite subset S of M containing X and all Steiner points of some Steiner minimal tree for X; this finite set S can trivially be turned into a Steiner hull by attaching one geodesic from M for each pair of its points. For the Steiner problem in rectilinear space, that is, a d-dimensional real space equipped with the metric associated with the 1-norm, finitely generated Steiner hulls have been described 7,12.

Contact Information Hans-J. Bandelt
Email: bandelt@math.uni-hamburg.de
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.107 • Server: MPWEB25
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)