Зарегистрироваться
Восстановить пароль
FAQ по входу

Hwang F.K., Richards D.S., Winter P. The Steiner Tree Problem

  • Файл формата djvu
  • размером 2,46 МБ
  • Добавлен пользователем
  • Отредактирован
Hwang F.K., Richards D.S., Winter P. The Steiner Tree Problem
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
  • Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.
  • Регистрация