North-Holland, 1992. — 353 p.The Steiner problem asks for a shortest network which spans a given set of points. Minimum spanning networks have been well-studied when all connections are required to be between the given points. The novelty of the Steiner tree problem is that new auxiliary points can be introduced between the original points so that a spanning network of all the points will be shorter than otherwise possible. These new points are called Steiner poiuts. It was soon recognized that locating these Steiner points was a difficult problem. It has opened a rich field of intriguing analyses and challenging associated problems. A large literature has arisen trying many different avenues to understand these problems. As these avenues diverged and more applications were found, the literature became more fragmented, leading to duplicated results and wasted effort. In this book we hope to draw together the many threads. Three major areas have emerged, which comprise the first three parts of this book. These are the Euclidean Steiner problem, the rectilznear Steiner problem, and the Steiner problem in networks. Since it can be shown tliat Steiner points in either the Euclidean or the rectilinear case belong to a finite set of points, these two problems can be regarded as special cases of the network problem. However, the study of these special geometries has led to the discovery of many interesting properties and better algorithms or heuristics, which would not have been found if they had been cast as network problems.Part I Euclidean Steiner Problem Introduction Exact Algorithms The Steiner Ratio Heuristics Special Terminal-Sets Generalizations Part II Steiner Problem in Networks Introduction Reductions Exact Algorithms Part Heuristics Polynomially Solvable Cases Generalizations Part III Rectilinear Steiner Problem Introduction Heuristic Algoritlinis Polynomially Solvable Cases Generalizations Routing Part IV Other Steiner Problems Steiner Trees in Other Metric Spaces Phylogenetic Trees
Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.