Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications by Marcus BrazilOptimal Interconnection Trees in the Plane: Theory, Algorithms and Applications by Marcus Brazil

Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications

byMarcus Brazil, Martin Zachariasen

Hardcover | April 23, 2015

Pricing and Purchase Info


Earn 553 plum® points

Prices and offers may vary in store


In stock online

Ships free on orders over $25

Not available in stores


This book explores fundamental aspects of geometric network optimisation with applications to a variety of real world problems. It presents, for the first time in the literature, a cohesive mathematical framework within which the properties of such optimal interconnection networks can be understood across a wide range of metrics and cost functions. The book makes use of this mathematical theory to develop efficient algorithms for constructing such networks, with an emphasis on exact solutions.

Marcus Brazil and Martin Zachariasen focus principally on the geometric structure of optimal interconnection networks, also known as Steiner trees, in the plane. They show readers how an understanding of this structure can lead to practical exact algorithms for constructing such trees.

The book also details numerous breakthroughs in this area over the past 20 years, features clearly written proofs, and is supported by 135 colour and 15 black and white figures. It will help graduate students, working mathematicians, engineers and computer scientists to understand the principles required for designing interconnection networks in the plane that are as cost efficient as possible.

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 a...
Title:Optimal Interconnection Trees in the Plane: Theory, Algorithms and ApplicationsFormat:HardcoverDimensions:344 pages, 23.5 × 15.5 × 0.01 inPublished:April 23, 2015Publisher:Springer-Verlag/Sci-Tech/TradeLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:3319139142

ISBN - 13:9783319139142


Table of Contents

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.

Editorial Reviews

"The book presents an interesting and quicklydeveloping area of research and will be useful for researchers working in thisarea and for those wanting to learn more about geometric Steiner tree problems."(Yongtang Shi, Mathematical Reviews, December, 2015)"The focus of this monograph is the geometricSteiner tree problem, i.e., how to optimally connect, in a geometric plane, acollection of n given terminals, together with an additional set of Steinerpoints, in terms of a measuring metric. . monograph is also intended as atextbook at a graduate level, thus comes with a decent collection of exercises,with varying difficulty degrees, at the end of each chapter, mostly assigned ina relevant context throughout the main text." (Zhizhang Shen, zbMATH 1319.05044,2015)