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.
|
 |
Median Hulls as Steiner Hulls in Rectilinear and Molecular Sequence Spaces
(Invited presentation)
| |
|
Median Hulls as Steiner Hulls in Rectilinear and Molecular Sequence Spaces
(Invited presentation)
Hans-J. Bandelt5 
| (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.
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|