Department of Computer Science DIKU > News > News 2015 > Martin Zachariasen has...
04 May 2015
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.
