Steiner Tree Problems In Computer Communication Networks

by Du, Dingzhu; Hu, Xiaodong

• ISBN13: 9789812791443
• ISBN10: 9812791442
• Format: Hardcover
• Copyright: 2008-02-20
• Publisher: World Scientific Pub Co Inc

Summary

"The Steiner tree problem is one of the most important combinatorial optimization problems. It has a long history that can be traced back to the famous mathematician Fermat (1601-1665). This book studies three significant breakthroughs on the Steiner tree problem that were achieved in the 1990s, and some important applications of Steiner tree problems in computer communication networks researched in the past fifteen years. It not only covers some of the most recent developments in Steiner tree problems, but also discusses various combinatorial optimization methods, thus providing a balance between theory and practice."--BOOK JACKET.

Table of Contents

Preface	p. v
Fundamentals of Classical Steiner Tree Problem
Minimax Approach and Steiner Ratio	p. 1
Minimax Approach	p. 3
Chebyshev Theorem	p. 4
Du-Hwang Theorem	p. 6
Geometric Inequalities	p. 10
Analysis of Approximation Performance	p. 13
Steiner Ratio in the Euclidean Plane	p. 14
Equivalent Minimax Problem	p. 15
Characteristic Area	p. 17
Inner Spanning Trees	p. 20
Critical Structure	p. 25
Hexagonal Trees	p. 29
Steiner Ratios in Other Metric Spaces	p. 34
Steiner Ratios in Euclidean Spaces	p. 34
Steiner Ratio in Rectilinear Spaces	p. 36
Steiner Ratio in Banach Spaces	p. 37
Discussions	p. 38
k-Steiner Ratios and Better Approximation Algorithms	p. 41
k-Steiner Ratio	p. 43
Upper Bound for k-Steiner Ratio	p. 44
Lower Bound for k-Steiner Ratio	p. 52
Approximations Better Than Minimum Spanning Tree	p. 59
Greedy Strategy	p. 61
Variable Metric Method	p. 70
Relative Greedy Strategy	p. 72
Preprocessing Technique	p. 73
Loss-Contracting Algorithm	p. 74
Discussions	p. 76
Geometric Partitions and Polynomial Time Approximation Schemes	p. 79
Guillotine Cut for Rectangular Partition	p. 80
1-Guillotine Cut	p. 85
m-Guillotine Cut	p. 88
Guillotine Cut for Rectilinear Steiner Minimum Tree	p. 90
Portals	p. 93
Portals for Rectilinear Steiner Minimum Tree	p. 94
Portals versus Guillotine Cuts	p. 97
Portals Integrated with Guillotine Cuts	p. 99
Two-Stage Portals	p. 104
Banyan and Spanner	p. 106
Discussions	p. 108
Grade of Service Steiner Tree Problem	p. 111
GoSST Problem in the Euclidean Plane	p. 114
Recursive Approximation Algorithm	p. 114
Branch-and-Bound Algorithm	p. 123
Minimum GoSST Problem in Graphs	p. 128
[beta]-Convex [alpha]-Approximation Steiner Tree Algorithms	p. 129
Algorithm for Two Non-Zero Rates	p. 132
Algorithm for Arbitrary Number of Rates	p. 135
Discussions	p. 137
Steiner Tree Problem for Minimal Steiner Points	p. 141
In the Euclidean Plane	p. 142
Complexity Study	p. 144
Steinerized Minimum Spanning Tree Algorithm	p. 146
Greedy Algorithm	p. 151
Polynomial Time Approximation Scheme	p. 155
Partition Strategy	p. 157
Approximation Scheme	p. 157
Exact Algorithm	p. 160
Connecting Local Forests and Boundary Points	p. 161
In the Rectilinear Plane	p. 162
Steinerized Minimum Spanning Tree Algorithm	p. 166
Greedy Algorithm	p. 170
In Metric Spaces	p. 172
Discussions	p. 175
Bottleneck Steiner Tree Problem	p. 177
Complexity Study	p. 178
Steinerized Minimum Spanning Tree Algorithm	p. 180
3-Restricted Steiner Tree Algorithm	p. 185
Discussions	p. 193
Steiner k-Tree and k-Path Routing Problems	p. 195
Problem Formulation and Complexity Study	p. 196
Problem Formulation	p. 196
Complexity Study	p. 198
Algorithms for k-Path Routing Problem	p. 203
Steiner Tree Based Algorithm	p. 203
Set Cover Based Algorithm	p. 208
Algorithms for k-Tree Routing Problem	p. 210
Hamilton Circuit Based Algorithm	p. 210
Steiner Tree Based Algorithm	p. 212
Discussions	p. 216
Steiner Tree Coloring Problem	p. 221
Maximum Tree Coloring	p. 222
Problem Formulation	p. 222
Inapproximability Analysis	p. 224
Approximation Algorithms	p. 229
For General Graphs	p. 229
For Special Graphs	p. 233
Minimum Tree Coloring	p. 235
Problem Formulation	p. 235
Inapproximability Analysis	p. 236
Approximation Algorithms	p. 241
For General Graphs	p. 242
For Special graphs	p. 247
Discussions	p. 250
Steiner Tree Scheduling Problem	p. 253
Minimum Aggregation Time	p. 255
Problem Formulation	p. 255
Complexity Analysis	p. 257
Greedy Algorithms	p. 263
Basic Algorithm	p. 264
Algorithms for Special Cases	p. 268
Partition Algorithm	p. 271
Aggregation Tree Construction	p. 271
Aggregation Time Schedule	p. 273
Performance Analysis of Algorithm	p. 274
Minimum Multicast Time Problem	p. 276
Problem Formulation	p. 276
Complexity Study	p. 278
Approximation Algorithm	p. 279
Performance Analysis of Algorithm	p. 282
Discussions	p. 283
Convergecast	p. 283
Multicast	p. 284
Convergecast and Multicast	p. 286
Survivable Steiner Network Problem	p. 287
Minimum k-Connected Steiner Networks	p. 289
Minimum Strong k-Connected Steiner Networks	p. 291
Minimum Weak k-Connected Steiner Networks	p. 295
Minimum Weak Two-Connected Steiner Networks	p. 296
Complexity Study	p. 299
Generalized Steiner Ratio	p. 301
In the Rectilinear Plane	p. 311
Minimum Weak Three-Edge-Connected Steiner Networks	p. 313
In the Euclidean Plane	p. 313
In the Rectilinear Plane	p. 323
Discussions	p. 325
Minimally k-Edge Connected Networks	p. 325
Minimum k-Edge Connected Spanning Networks	p. 326
Minimum k-Vertex Connected Spanning Networks	p. 328
Minimum Spanning Network of Nonuniform Connectivity	p. 330
More Steiner Tree Related Problems	p. 331
Bibliography	p. 337
Index	p. 355
Table of Contents provided by Ingram. All Rights Reserved.