Nicht aus der Schweiz? Besuchen Sie lehmanns.de

Optimal Interconnection Trees in the Plane (eBook)

Theory, Algorithms and Applications
eBook Download: PDF
2015 | 2015
XVII, 344 Seiten
Springer International Publishing (Verlag)
978-3-319-13915-9 (ISBN)

Lese- und Medienproben

Optimal Interconnection Trees in the Plane - Marcus Brazil, Martin Zachariasen
Systemvoraussetzungen
63,06 inkl. MwSt
(CHF 61,60)
Der eBook-Verkauf erfolgt durch die Lehmanns Media GmbH (Berlin) zum Preis in Euro inkl. MwSt.
  • Download sofort lieferbar
  • Zahlungsarten anzeigen
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 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.

Erscheint lt. Verlag 13.4.2015
Reihe/Serie Algorithms and Combinatorics
Verlagsort Cham
Sprache englisch
Themenwelt Mathematik / Informatik Informatik Programmiersprachen / -werkzeuge
Mathematik / Informatik Mathematik
Technik
Schlagworte algorithms • combinatorics • Computational Geometry • Network Optimization • Steiner trees
ISBN-10 3-319-13915-0 / 3319139150
ISBN-13 978-3-319-13915-9 / 9783319139159
Haben Sie eine Frage zum Produkt?
PDFPDF (Wasserzeichen)

DRM: Digitales Wasserzeichen
Dieses eBook enthält ein digitales Wasser­zeichen und ist damit für Sie persona­lisiert. Bei einer missbräuch­lichen Weiter­gabe des eBooks an Dritte ist eine Rück­ver­folgung an die Quelle möglich.

Dateiformat: PDF (Portable Document Format)
Mit einem festen Seiten­layout eignet sich die PDF besonders für Fach­bücher mit Spalten, Tabellen und Abbild­ungen. Eine PDF kann auf fast allen Geräten ange­zeigt werden, ist aber für kleine Displays (Smart­phone, eReader) nur einge­schränkt geeignet.

Systemvoraussetzungen:
PC/Mac: Mit einem PC oder Mac können Sie dieses eBook lesen. Sie benötigen dafür einen PDF-Viewer - z.B. den Adobe Reader oder Adobe Digital Editions.
eReader: Dieses eBook kann mit (fast) allen eBook-Readern gelesen werden. Mit dem amazon-Kindle ist es aber nicht kompatibel.
Smartphone/Tablet: Egal ob Apple oder Android, dieses eBook können Sie lesen. Sie benötigen dafür einen PDF-Viewer - z.B. die kostenlose Adobe Digital Editions-App.

Buying eBooks from abroad
For tax law reasons we can sell eBooks just within Germany and Switzerland. Regrettably we cannot fulfill eBook-orders from other countries.

Mehr entdecken
aus dem Bereich
Das Handbuch für Webentwickler

von Philip Ackermann

eBook Download (2023)
Rheinwerk Computing (Verlag)
CHF 48,75
Das umfassende Handbuch

von Johannes Ernesti; Peter Kaiser

eBook Download (2023)
Rheinwerk Computing (Verlag)
CHF 43,85