Shortest Connectivity: An Introduction with Applications in Phylogeny

Dietmar Cieslik0387235388, 9780387235387, 9780387235394

“This volume is an introduction to the theory of shortest connectivity, as the core of the so-called “Geometric Network Design Problems”, where the general problem can be stated as follows: given a configuration of vertices and/or edges, find a network which contains these objects, satisfies some predetermined requirements, and which minimizes a given objective function that depends on several distance measures. A new application of shortest connectivity is also discussed, namely to create trees which reflect the evolutionary history of “living entities”. The aim in this graduate level text is to outline the key mathematical concepts that underpin these important questions in applied mathematics. These concepts involve discrete mathematics (particularly graph theory), optimization, computer science, and several ideas in biology.

---

Table of contents :
front-matter……Page 1
1Two Classical Optimization Problems……Page 10
2Gauss’ Question……Page 30
3What Does Solution Mean……Page 64
4Network Design Problems……Page 92
5A New Challenge The Phylogeny……Page 132
6An Analysis of Steiner’s Problem in Phylogenetic Spaces……Page 180
7Tree Building Algorithms……Page 218
back-matter……Page 239