Optimal Interconnection Trees in the Plane (eBook)

Marcus Brazil is Associate Professor and Reader at the Melbourne School of Engineering, The University of Melbourne, with a background in pure mathematics. He has worked on Steiner trees and network optimization problems for about 18 years, and has written more than 60 papers in this area, both on the theory of optimal network design and on industrial applications to Wireless Sensor Networks, Telecommunications, VLSI Physical Design, and Underground Mining Planning.Martin Zachariasen is Head of Department and Professor at the Department of Computer Science, University of Copenhagen. He has worked on heuristics and exact methods for classical NP-hard problems, such as the geometric Steiner Tree Problem, as well as other optimization problems. His general research interests are in experimental algorithmics and computational combinatorial optimization, in particular related to VLSI design. As well as writing more than 40 papers on these topics, he is one of the developers of GeoSteiner, which is by far the most efficient software for solving a range of geometric Steiner tree problems.

Preface.-  1 Euclidean and Minkowski Steiner Trees.- 1.2 Algorithms for a given Steiner topology.-  1.3 Global properties of minimum Steiner trees.- 1.4 GeoSteiner algorithm.- 1.5 Efficient constructions for special terminal sets.- 1.6 Steiner trees in Minkowski planes.-  1.7 Applications and extensions.- 2 Fixed Orientation Steiner Trees.- 2.1 Fixed orientation networks.- 2.2 Local properties for Steiner points.- 2.3 Local properties for full components.- 2.4 Algorithms for a given topology.- 2.5 Global properties of minimum Steiner trees.- 2.6 GeoSteiner algorithm.- 2.7 Applications and extensions.- 3 Rectilinear Steiner Trees.- 3.1 Local properties for Steiner points and full components.- 3.2 Global properties for minimum Steiner trees.- 3.3 GeoSteiner algorithm.- 3.4 FLUTE algorithm.- 3.5 Efficient constructions for special terminal sets.- 3.6 Applications and extensions.- 4 Steiner Trees with Other Costs and Constraints.- 4.1 The gradient-constrained Steiner tree problem.- 4.2 Obstacle-avoiding Steiner trees.- 4.3 Bottleneck and general k-Steiner tree problems.- 4.4 Trees Minimizing Flow Costs.- 4.5 Related topics.- 5 Steiner Trees in Graphs and Hypergraphs.- 5.1 Steiner trees in graphs.- 5.2 Minimum spanning trees in hypergraphs.- 5.3 Steiner trees in hypergraphs.- A Appendix.