Muutke küpsiste eelistusi

Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications 2015 ed. [Kõva köide]

,
  • Formaat: Hardback, 344 pages, kõrgus x laius: 235x155 mm, kaal: 7342 g, 135 Illustrations, color; 15 Illustrations, black and white; XVII, 344 p. 150 illus., 135 illus. in color., 1 Hardback
  • Sari: Algorithms and Combinatorics 29
  • Ilmumisaeg: 23-Apr-2015
  • Kirjastus: Springer International Publishing AG
  • ISBN-10: 3319139142
  • ISBN-13: 9783319139142
Teised raamatud teemal:
  • Kõva köide
  • Hind: 48,70 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Tavahind: 57,29 €
  • Säästad 15%
  • Raamatu kohalejõudmiseks kirjastusest kulub orienteeruvalt 2-4 nädalat
  • Kogus:
  • Lisa ostukorvi
  • Tasuta tarne
  • Tellimisaeg 2-4 nädalat
  • Lisa soovinimekirja
Optimal Interconnection Trees in the Plane: Theory, Algorithms and Applications 2015 ed.Suurem pilt
  • Formaat: Hardback, 344 pages, kõrgus x laius: 235x155 mm, kaal: 7342 g, 135 Illustrations, color; 15 Illustrations, black and white; XVII, 344 p. 150 illus., 135 illus. in color., 1 Hardback
  • Sari: Algorithms and Combinatorics 29
  • Ilmumisaeg: 23-Apr-2015
  • Kirjastus: Springer International Publishing AG
  • ISBN-10: 3319139142
  • ISBN-13: 9783319139142
Teised raamatud teemal:
Püsilink: https://www.kriso.ee/db/9783319139142.html
Märksõnad:
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.

Arvustused

The book presents an interesting and quickly developing area of research and will be useful for researchers working in this area 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 geometric Steiner tree problem, i.e., how to optimally connect, in a geometric plane, a collection of n given terminals, together with an additional set of Steiner points, in terms of a measuring metric. monograph is also intended as a textbook at a graduate level, thus comes with a decent collection of exercises, with varying difficulty degrees, at the end of each chapter, mostly assigned in a relevant context throughout the main text. (Zhizhang Shen, zbMATH 1319.05044, 2015)

1 Euclidean and Minkowski Steiner Trees 1(82)
1.1 Euclidean Steiner Trees and Local Properties
1(14)
1.1.1 The Fermat-Torricelli Problem
1(4)
1.1.2 The Steiner Tree Problem
5(4)
1.1.3 Topologies and Full Components
9(6)
1.2 Algorithms for a Given Steiner Topology
15(7)
1.2.1 The Melzak-Hwang Algorithm
15(6)
1.2.2 Relatively Minimal Tree for a Given Full Steiner Topology
21(1)
1.3 Global Properties of Minimum Steiner Trees
22(17)
1.3.1 Minimum Spanning Trees and the Steiner Ratio
23(2)
1.3.2 Structural Properties
25(6)
1.3.3 Computational Complexity
31(8)
1.4 GeoSteiner Algorithm
39(13)
1.4.1 Top-Level Algorithm
39(1)
1.4.2 Enumeration of Equilateral Points, Branches and Branch Trees
40(3)
1.4.3 Pruning of Equilateral Points/Branches and Full Steiner Trees
43(8)
1.4.4 Concatenation of Full Steiner Trees
51(1)
1.5 Efficient Constructions for Special Terminal Sets
52(9)
1.5.1 Terminals Constrained to Circles or Curves
52(5)
1.5.2 Terminals on Rectangular Lattices
57(4)
1.6 Steiner Trees in Minkowski Planes
61(12)
1.6.1 Steiner Points of Degree 3
63(4)
1.6.2 Steiner Points of Degree > or = to 4
67(6)
1.7 Applications and Extensions
73(10)
1.7.1 Applications
73(3)
1.7.2 Extensions to Higher Dimensions
76(7)
2 Fixed Orientation Steiner Trees 83(68)
2.1 Fixed Orientation Networks
84(6)
2.1.1 Fixed Orientation Metrics
84(4)
2.1.2 The Fixed Orientation Steiner Tree Problem
88(2)
2.2 Local Properties of Steiner Points
90(13)
2.2.1 Steiner Points for Uniform Orientation Metrics
90(3)
2.2.2 Steiner Points for General Fixed Orientations
93(10)
2.3 Local Properties of Full Components
103(15)
2.3.1 Direction Sets
103(3)
2.3.2 Degree 4 Steiner Points
106(2)
2.3.3 Zero-Shifts
108(8)
2.3.4 Canonical Forms
116(2)
2.4 Algorithms for a Given Topology
118(9)
2.4.1 Linear Programming Formulation
118(1)
2.4.2 Algorithms Based on the Canonical Form
119(5)
2.4.3 Algorithms for Flexibility Polygons
124(3)
2.5 Global Properties of Minimum Steiner Trees
127(12)
2.5.1 Steiner Ratios
127(2)
2.5.2 Generalised Hanan Grid Reduction
129(2)
2.5.3 Computational Complexity
131(8)
2.6 GeoSteiner Algorithm
139(4)
2.6.1 Top-Level FST Generation Algorithm
139(1)
2.6.2 Pruning of Branch Trees and Full Steiner Trees
140(3)
2.7 Applications and Extensions
143(8)
2.7.1 Printed Circuit Boards and Channel Routing
144(2)
2.7.2 General Routing in Chip Design
146(5)
3 Rectilinear Steiner Trees 151(68)
3.1 Local Properties of Steiner Points and Full Components
152(12)
3.1.1 Basic Definitions and Properties
152(4)
3.1.2 Hwang Form for Full Components
156(8)
3.2 Global Properties of Minimum Steiner Trees
164(22)
3.2.1 Steiner Ratio
164(2)
3.2.2 Hanan Grid Reduction
166(3)
3.2.3 Empty Regions
169(3)
3.2.4 Bounds on the Number of Full Components
172(7)
3.2.5 Computational Complexity
179(5)
3.2.6 Equivalence to Other Problems with a Pair of Fixed Orientations
184(2)
3.3 GeoSteiner Algorithm
186(7)
3.3.1 Top-Level FST Generation Algorithm
187(1)
3.3.2 FST Independent Preprocessing
188(3)
3.3.3 Growing Hwang Form Full Steiner Trees
191(2)
3.4 FLUTE Algorithm
193(5)
3.4.1 Position Sequence and Wire Length Vectors
194(2)
3.4.2 Basic FLUTE Algorithm
196(1)
3.4.3 Optimised FLUTE Algorithm
196(1)
3.4.4 Enumeration of Minimal Wire Length Vectors
197(1)
3.5 Efficient Constructions for Special Terminal Sets
198(5)
3.5.1 Terminals Constrained to Parallel Lines
198(2)
3.5.2 Terminals on Rectilinearly Convex Polygons
200(2)
3.5.3 Terminals Constrained to Curves
202(1)
3.6 Applications and Extensions
203(16)
3.6.1 Physical Design of Circuits
204(5)
3.6.2 Extensions Motivated by the Physical Design of Circuits
209(5)
3.6.3 Extensions to Higher Dimensions
214(5)
4 Steiner Trees with Other Cost Functions and Constraints 219(82)
4.1 The Gradient-Constrained Steiner Tree Problem
219(13)
4.1.1 Basic Properties of Gradient-Constrained Steiner Trees
220(4)
4.1.2 Construction of Gradient-Constrained Steiner Trees
224(4)
4.1.3 Applications
228(4)
4.2 Obstacle-Avoiding Steiner Trees
232(19)
4.2.1 Steiner Trees with Polygonal Obstacles
233(4)
4.2.2 Obstacle-Avoiding Euclidean Steiner Trees
237(2)
4.2.3 Obstacle-Avoiding Fixed Orientation and Rectilinear Steiner Trees
239(8)
4.2.4 GeoSteiner Algorithm
247(2)
4.2.5 Applications and Extensions
249(2)
4.3 Bottleneck and General k-Steiner Tree Problems
251(26)
4.3.1 The Generalised k-Steiner Tree Problem
252(11)
4.3.2 An Algorithm for the Generalised k-Steiner Tree Problem
263(6)
4.3.3 Bottleneck Steiner Trees for the Euclidean and Other Metrics
269(4)
4.3.4 Applications
273(4)
4.4 Trees Minimising Flow Costs
277(12)
4.4.1 Gilbert Networks and Arborescences
277(9)
4.4.2 Applications and Extensions
286(3)
4.5 Related Topics
289(12)
4.5.1 Power-p Steiner Trees
289(3)
4.5.2 Node-Weighted Steiner Trees
292(3)
4.5.3 Rotationally Optimal Steiner Trees
295(6)
5 Steiner Trees in Graphs and Hypergraphs 301(18)
5.1 Steiner Trees in Graphs
302(9)
5.1.1 Graph Reductions
304(1)
5.1.2 Dynamic Programming
305(1)
5.1.3 Integer Programming
306(5)
5.2 Spanning Trees and Steiner Trees in Hypergraphs
311(8)
5.2.1 Spanning Trees in Hypergraphs
312(3)
5.2.2 Steiner Trees in Hypergraphs
315(4)
Bibliography 319(20)
Index 339
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.