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

Prömel H.J., Steger A. The Steiner Tree Problem. A Tour through Graphs, Algorithms, and Complexity

  • Файл формата pdf
  • размером 7,23 МБ
  • Добавлен пользователем
  • Отредактирован
Prömel H.J., Steger A. The Steiner Tree Problem. A Tour through Graphs, Algorithms, and Complexity
Vieweg, 2002. — 251 p.
"A very simple but instructive problem was treated by Jacob Steiner, the famous representative of geometry at the University of Berlin in the early nineteenth century. Three villages A,B ,C are to be joined by a system of roads of minimum length." Due to this remark of Courant and Robbins (1941), a problem received its name that actually reaches two hundred years further back and should more appropriately be attributed to the French mathematician Pierre Fermat. At the end of his famous treatise Minima and Maxima he raised the question to find for three given points in the plane a fourth one in such a way that the sum of its distances to the given points is minimized - that is, to solve the problem mentioned above in its mathematical abstraction. It is known that Evangelista Torricelli had found a geometrical solution for this problem already before 1640.
During the last centuries this problem was rediscovered and generalized by many mathematicians, including Jacob Steiner. Nowadays the term Steiner problem refers to a problem where a set of given points p1, … ,pn have to be connected in such a way that (i) any two of the given points are joined and (ii) the total length (measured with respect to some predefined cost function) is minimized. The importance of the Steiner problem stems from the fact that it has important applications in as diverse areas as VLSI-layout and the study of phylogenetic trees. While this might be reason enough to write a book about the Steiner problem, our motivation is a different one.
To handle the modern versions of the Steiner problem one has to combine methods, tools, and techniques from many different areas. The resulting progress has uncovered fascinating connections between and within graph theory, the study of algorithms, and complexity theory. This single problem can thus serve perfectly as a motivation and link for an introduction to these three fields. An additional challenging aspect is that these fields form a bridge between mathematics and computer science. We thus also have to combine different views, approaches and notational conventions within these two communities. Accordingly, we tried to present a coherent introduction which exhibits the interplay between these areas. Hopefully, it will stimulate the reader's interest and appetite for a broader perspective and deeper understanding of the subject. In order to at least partially meet this desire, every chapter closes with an "excursion". These sections are designed to reinforce the concepts and methods introduced for the Steiner problem by placing them in a broader context. Topics for these excursions are themes which we feel represent important and fascinating aspects and are likely to provide motivation for further studies for the reader. Each excursion is self-contained and is not presumed in later chapters.
The book is organized as follows. In the first three chapters we provide a short introduction to the three areas graph theory, algorithms, and complexity. Each introduction could easily fill a book by itself. We therefore had to concentrate ourselves on notions and results necessary for a thorough understanding of the themes in this book. The following seven chapters then cover various aspects of the Steiner problem in particular and algorithm design in general. Every chapter closes with bibliographical notes and a list of problems. Due to space restrictions our notes are far from exhaustive: we do attribute major results and proofs, but beyond that we aim at little more than presenting some selective suggestions for further readings. The problems are aimed at testing the understanding of the concepts of the chapter, including the excursion. A star indicates that the problem is more difficult. It usually requires some creativity and a more lengthy argument.
Basics I: Graphs
Basics II: Algorithms
Basics III: Complexity
Special Terminal Sets
Exact Algorithms
Approximation Algorithms
Randomness Helps
Limits of Approximability
Geometric Steiner Problems
  • Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт используя форму сверху.
  • Регистрация