Martin Zachariasen has released a new book about the Steiner tree problem
Steiner trees
Former Head of the Computer Science Department, Martin Zachariasen, has just co-authored a new book about his specialty, the Steiner tree problem. The book has the title Optimal Interconnection Trees in the Plane.
Martin Zachariasen just started his new job as Dean of the Faculty of Science at the University of Southern Denmark on Monday 4th of May 2015, but for many years preceding this, Martin had a busy job as Head of the Department of Computer Science at the University of Copenhagen (DIKU).
Despite the pressure and responsibility of leading the Department of Computer Science, Martin still found time for earning a Doctor’s degree on the algorithmic problem of the Euclidian Steiner tree. The Doctor’s thesis has now become one of four main chapters in the book, Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications, published by Springer in 2015 and with Marcus Brazil as co-author.
Martin Zachariasen on his new book
- The story behind the book is this: In 2010 I defended my Doctor’s thesis about the so-called fixed-orientation Steiner tree problem. After the defense, both opponents, Professor Ronald Graham and Professor Jens Vygen, proposed that I write a book on the subject. I allied myself with a good colleague of mine from the University of Melbourne, Professor Marcus Brazil, and we started on the project in 2011. We contacted Springer, and they expressed interest in publishing the book in one of their well-known series.
- The book is about different variants of the Steiner tree problem in the plane. The material from my Doctor’s thesis now constitutes one of the four main chapters in the book.
- Marcus and I decided that the book should be ‘self-contained’, meaning that it contains all central mathematical proofs concerning the properties of the Steiner tree including algorithms to solve the problem. We also took great care to produce a lot of high quality figures, and we chose – and got permission from the publisher – to use colors for most of the figures. This ought to ease the reading of the book.
- The book features a great number of details that have never before been published in a book, for instance
- a comprehensive updated description of the historical origin of the problem
- complete proofs for the NP-hardness of the problem
- detailed descriptions of the most relevant exact algorithms.
Related News
The Steiner tree explained
The Steiner tree problem is about finding the shortest path between a set of points.
As opposed to minimum spanning trees (figure a) where all paths go through the points themselves, Steiner trees (figures b and c) allow you to insert ekstra mediating points (Steiner points) resulting in a shorter cumulative length. This, however, also makes the problem so much the harder (even NP-complete) since it is difficult to calculate how many extra mediating points there should be and where they should be placed.
Figure a) represents a minimum spanning tree, figure b) is an Euclidian Steiner tree and figure c) is a rectilinear Steiner tree.
The example shows how many calculations are needed to change the position of just one point in the Steiner tree.
A formal definition
If N is a final set of points in the plane, the Euclidian Steiner tree problem is: Find a set of line segments so that all the points are connected with each other and so that the total Euclidian length of the line segments is minimized.