Who is Who in Phylogenetic Networks

Publications of Ingo Althöfer     Order by:   Type | Year

Associated keywords

NP-complete optimal-realization realization

1986

1 Ingo Althöfer. On optimal realizations of finite metric spaces by graphs. In Discrete and Computational Geometry, Vol. 3(1):103-122, 1986. Keywords: NP complete, optimal realization, realization. Note: http://dx.doi.org/10.1007/BF02187901.         Toggle abstract "Graph realizations of finite metric spaces have widespread applications, for example, in biology, economics, and information theory. The main results of this paper are: 1. Finding optimal realizations of integral metrics (which means all distances are integral) is NP-complete. 2. There exist metric spaces with a continuum of optimal realizations. Furthermore, two conditions necessary for a weighted graph to be an optimal realization are given and an extremal problem arising in connection with the realization problem is investigated. © 1988 Springer-Verlag New York Inc."