Dietmar Cieslik - Böcker

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.

This book is the result of many years of research into Steiner's problem and its relatives in theory and application. Starting with investigations of shortest networks for VLSI layout and, on the other hand, for certain facility location problems, the author has found many common properties for Steiner's problem in various spaces. The purpose of the book is to sum up and generalize many of these results for arbitrary finite-dimensional Banach spaces. It shows that we can create a homogeneous and general theory when we consider two dimensions of such spaces, and that we can find many facts which are helpful in attacking Steiner's problem in the higher-dimensional cases. The author examines the underlying mathematical properties of this network design problem and demonstrates how it can be attacked by various methods of geometry, graph theory, calculus, optimization and theoretical computer science. The work should be of interest to all mathematicians and users of applied graph theory.

This volume concerns finding a shortest interconnecting network for a finite set of points in a metric space. A solution must be a tree, which is called a Steiner Minimal Tree (SMT), and may contain vertices different from the points which are to be connected. Steiner's Problem is one of the most famous combinatorial--geometrical problems, but unfortunately it is very difficult in terms of combinatorial structure as well as computational complexity. However, if only a Minimum Spanning Tree (MST) without additional vertices in the interconnecting network is sought, then it is simple to solve. So it is of interest to know what the error is if an MST is constructed instead of an SMT. The worst case for this ratio running over all finite sets is called the Steiner ratio of the space. The book concentrates on investigating the Steiner ratio. The goal is to determine, or at least estimate, the Steiner ratio for many different metric spaces. The author shows that the description of the Steiner ratio contains many questions from geometry, optimization, and graph theory. Researchers in network design, applied optimization, and design of algorithms should find this book useful.

This book is the result of 18 years of research into Steiner's problem and its relatives in theory and application. Starting with investigations of shortest networks for VLSI layout and, on the other hand, for certain facility location problems, the author has found many common properties for Steiner's problem in various spaces. The purpose of the book is to sum up and generalize many of these results for arbitrary finite-dimensional Banach spaces. It shows that we can create a homogeneous and general theory when we consider two dimensions of such spaces, and that we can find many facts which are helpful in attacking Steiner's problem in the higher-dimensional cases. The author examines the underlying mathematical properties of this network design problem and demonstrates how it can be attacked by various methods of geometry, graph theory, calculus, optimization and theoretical computer science. Audience: All mathematicians and users of applied graph theory.

Steiner's Problem concerns finding a shortest interconnecting network for a finite set of points in a metric space. A solution must be a tree, which is called a Steiner Minimal Tree (SMT), and may contain vertices different from the points which are to be connected. Steiner's Problem is one of the most famous combinatorial-geometrical problems, but unfortunately it is very difficult in terms of combinatorial structure as well as computational complexity. However, if only a Minimum Spanning Tree (MST) without additional vertices in the interconnecting network is sought, then it is simple to solve. So it is of interest to know what the error is if an MST is constructed instead of an SMT. The worst case for this ratio running over all finite sets is called the Steiner ratio of the space. The book concentrates on investigating the Steiner ratio. The goal is to determine, or at least estimate, the Steiner ratio for many different metric spaces. The author shows that the description of the Steiner ratio contains many questions from geometry, optimization, and graph theory. Audience: Researchers in network design, applied optimization, and design of algorithms.