Skip to main content
Top

2015 | Book

Optimal Interconnection Trees in the Plane

Theory, Algorithms and Applications

insite
SEARCH

About this book

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.

Table of Contents

Frontmatter
Chapter 1. Euclidean and Minkowski Steiner Trees
Abstract
This chapter begins with a comprehensive study of the Euclidean Steiner tree problem. This is the most intuitively appealing of the Steiner tree problems and the one with the longest history. The first two sections of the chapter present the fundamental theory, which then leads into topics including computational complexity, algorithmic approaches and special cases. The chapter then looks at how some of the fundamental properties of Euclidean Steiner trees can be generalised to arbitrary norms, establishing some key general properties which are drawn on in the later chapters.
Marcus Brazil, Martin Zachariasen
Chapter 2. Fixed Orientation Steiner Trees
Abstract
This chapter covers the comparatively recent theory of Steiner trees for fixed orientation metrics. This is equivalent to solving the Steiner tree problem under a norm in which the unit ball is a centrally symmetric polygon. The chapter builds on some of the more general properties of normed Steiner trees from Chapter 1 Here the fundamental theory is developed in the first three sections, followed by discussions of global properties and algorithms.
Marcus Brazil, Martin Zachariasen
Chapter 3. Rectilinear Steiner Trees
Abstract
The rectilinear Steiner tree problem, which is the most important form of the Steiner tree problem in terms of current applications (mostly involving the design of microchips), is the subject of this chapter. We have attempted to make the chapter reasonably self-contained, although a familiarity with some of the concepts in the earlier chapters, such as direction sets and canonical forms, is assumed. Here the fundamental properties are described in the first section, followed by global properties, two different algorithmic approaches and a discussion of special sets of points for which polynomial-time algorithms exist.
Marcus Brazil, Martin Zachariasen
Chapter 4. Steiner Trees with Other Cost Functions and Constraints
Abstract
In this chapter we look at Steiner tree problems that involve other cost functions and constraints (beyond those discussed in the first three chapters) but that still can be solved exactly by exploiting the geometric properties of minimal solutions. We focus particularly on four types of Steiner tree problems: the gradient-constrained Steiner tree problem, which serves as another example of an exactly solvable Steiner tree problem in a Minkowski plane with useful applications; the obstacle-avoiding Steiner tree problem, which is an important variation of the Steiner tree problem with applications in the physical design of microchips; bottleneck and other k-Steiner tree problems, where there is a given bound on the number of Steiner points; and Steiner tree problems optimising a cost associated with flow on the network.
Marcus Brazil, Martin Zachariasen
Chapter 5. Steiner Trees in Graphs and Hypergraphs
Abstract
In this chapter we consider two combinatorial versions of the Steiner tree problem: the Steiner tree problem in graphs and the Steiner tree problem in hypergraphs. Also, we consider the minimum spanning tree problem in hypergraphs. Although this book focuses on geometric interconnection problems in the plane, these combinatorial problems are included for several reasons. Firstly, the Steiner tree problem in graphs is probably the best studied of all the many variants of the Steiner tree problem. Secondly, the fixed orientation Steiner tree problem in the plane (and specifically the rectilinear Steiner tree problem in the plane) can be reduced to the Steiner tree problem in graphs. Thirdly, the full Steiner tree concatenation phase of GeoSteiner, the most efficient exact algorithm for computing minimum Steiner trees in the plane, can be reduced to either the Steiner tree problem in graphs or the minimum spanning tree problem in hypergraphs.
Marcus Brazil, Martin Zachariasen
Backmatter
Metadata
Title
Optimal Interconnection Trees in the Plane
Authors
Marcus Brazil
Martin Zachariasen
Copyright Year
2015
Electronic ISBN
978-3-319-13915-9
Print ISBN
978-3-319-13914-2
DOI
https://doi.org/10.1007/978-3-319-13915-9

Premium Partner