Steiner tree problems in computer communication networks

Dingzhu Du, Xiaodong Hu9812791442, 9789812791443, 9789812791450

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.
Contents: Minimax Approach and Steiner Ratio; k-Steiner Ratios and Better Approximation Algorithms; Geometric Partitions and Polynomial Time Approximation Schemes; Grade of Service Steiner Tree Problem; Steiner Tree Problem for Minimal Steiner Points; Bottleneck Steiner Tree Problem; Steiner k-Tree and k-Path Routing Problems; Steiner Tree Coloring Problem; Steiner Tree Scheduling Problem; Survivable Steiner Network Problem.

---

Table of contents :
Contents……Page 10
Preface……Page 6
1. Minimax Approach and Steiner Ratio……Page 15
1.1 Minimax Approach……Page 17
1.1.1 Chebyshev Theorem……Page 18
1.1.2 Du-Hwang Theorem……Page 20
1.1.3 Geometric Inequalities……Page 24
1.1.4 Analysis of Approximation Performance……Page 27
1.2 Steiner Ratio in the Euclidean Plane……Page 28
1.2.1 Equivalent Minimax Problem……Page 29
1.2.2 Characteristic Area……Page 31
1.2.3 Inner Spanning Trees……Page 34
1.2.4 Critical Structure……Page 39
1.2.5 Hexagonal Trees……Page 43
1.3.1 Steiner Ratios in Euclidean Spaces……Page 48
1.3.2 Steiner Ratio in Rectilinear Spaces……Page 50
1.3.3 Steiner Ratio in Banach Spaces……Page 51
1.4 Discussions……Page 52
2. k-Steiner Ratios and Better Approximation Algorithms……Page 55
2.1 k-Steiner Ratio……Page 57
2.1.1 Upper Bound for k-Steiner Ratio……Page 58
2.1.2 Lower Bound for k-Steiner Ratio……Page 66
2.2 Approximations Better Than Minimum Spanning Tree……Page 73
2.2.1 Greedy Strategy……Page 75
2.2.2 Variable Metric Method……Page 84
2.2.3 Relative Greedy Strategy……Page 86
2.2.4 Preprocessing Technique……Page 87
2.2.5 Loss-Contracting Algorithm……Page 88
2.3 Discussions……Page 90
3. Geometric Partitions and Polynomial Time Approximation Schemes……Page 93
3.1 Guillotine Cut for Rectangular Partition……Page 94
3.1.1 1-Guillotine Cut……Page 99
3.1.2 m-Guillotine Cut……Page 102
3.1.3 Guillotine Cut for Rectilinear Steiner Minimum Tree……Page 104
3.2 Portals……Page 107
3.2.1 Portals for Rectilinear Steiner Minimum Tree……Page 108
3.2.2 Portals versus Guillotine Cuts……Page 111
3.2.3 Portals Integrated with Guillotine Cuts……Page 113
3.2.4 Two-Stage Portals……Page 118
3.3 Banyan and Spanner……Page 120
3.4 Discussions……Page 122
4. Grade of Service Steiner Tree Problem……Page 125
4.1.1 Recursive Approximation Algorithm……Page 128
4.1.2 Branch-and-Bound Algorithm……Page 137
4.2 Minimum GoSST Problem in Graphs……Page 142
4.2.1 -Convex -Approximation Steiner Tree Algorithms……Page 143
4.2.2 Algorithm for Two Non-Zero Rates……Page 146
4.2.3 Algorithm for Arbitrary Number of Rates……Page 149
4.3 Discussions……Page 151
5. Steiner Tree Problem for Minimal Steiner Points……Page 155
5.1 In the Euclidean Plane……Page 156
5.1.1 Complexity Study……Page 158
5.1.2 Steinerized Minimum Spanning Tree Algorithm……Page 160
5.1.3 Greedy Algorithm……Page 165
5.1.4 Polynomial Time Approximation Scheme……Page 169
5.1.4.2 Approximation Scheme……Page 171
5.1.4.3 Exact Algorithm……Page 174
5.1.4.4 Connecting Local Forests and Boundary Points……Page 175
5.2 In the Rectilinear Plane……Page 176
5.2.1 Steinerized Minimum Spanning Tree Algorithm……Page 180
5.2.2 Greedy Algorithm……Page 184
5.3 In Metric Spaces……Page 186
5.4 Discussions……Page 189
6. Bottleneck Steiner Tree Problem……Page 191
6.1 Complexity Study……Page 192
6.2 Steinerized Minimum Spanning Tree Algorithm……Page 194
6.3 3-Restricted Steiner Tree Algorithm……Page 199
6.4 Discussions……Page 207
7. Steiner k-Tree and k-Path Routing Problems……Page 209
7.1.1 Problem Formulation……Page 210
7.1.2 Complexity Study……Page 212
7.2.1 Steiner Tree Based Algorithm……Page 217
7.2.2 Set Cover Based Algorithm……Page 222
7.3.1 Hamilton Circuit Based Algorithm……Page 224
7.3.2 Steiner Tree Based Algorithm……Page 226
7.4 Discussions……Page 230
8. Steiner Tree Coloring Problem……Page 235
8.1.1 Problem Formulation……Page 236
8.1.2 Inapproximability Analysis……Page 238
8.1.3.1 For General Graphs……Page 243
8.1.3.2 For Special Graphs……Page 247
8.2.1 Problem Formulation……Page 249
8.2.2 Inapproximability Analysis……Page 250
8.2.3 Approximation Algorithms……Page 255
8.2.3.1 For General Graphs……Page 256
8.2.3.2 For Special graphs……Page 261
8.3 Discussions……Page 264
9. Steiner Tree Scheduling Problem……Page 267
9.1.1 Problem Formulation……Page 269
9.1.2 Complexity Analysis……Page 271
9.1.3 Greedy Algorithms……Page 277
9.1.3.1 Basic Algorithm……Page 278
9.1.3.2 Algorithms for Special Cases……Page 282
9.1.4.1 Aggregation Tree Construction……Page 285
9.1.4.2 Aggregation Time Schedule……Page 287
9.1.5 Performance Analysis of Algorithm……Page 288
9.2.1 Problem Formulation……Page 290
9.2.2 Complexity Study……Page 292
9.2.3 Approximation Algorithm……Page 293
9.2.4 Performance Analysis of Algorithm……Page 296
9.3.1 Convergecast……Page 297
9.3.2 Multicast……Page 298
9.3.3 Convergecast and Multicast……Page 300
10. Survivable Steiner Network Problem……Page 301
10.1 Minimum k-Connected Steiner Networks……Page 303
10.1.1 Minimum Strong k-Connected Steiner Networks……Page 305
10.1.2 Minimum Weak k-Connected Steiner Networks……Page 309
10.2 Minimum Weak Two-Connected Steiner Networks……Page 310
10.2.1 Complexity Study……Page 313
10.2.2 Generalized Steiner Ratio……Page 315
10.2.3 In the Rectilinear Plane……Page 325
10.3.1 In the Euclidean Plane……Page 327
10.3.2 In the Rectilinear Plane……Page 337
10.4.1 Minimally k-Edge Connected Networks……Page 339
10.4.4 Minimum Spanning Network of Nonuniform Connectivity……Page 14
10.4.3 Minimum k-Vertex Connected Spanning Networks……Page 342
Appendix A More Steiner Tree Related Problems……Page 345
Bibliography……Page 351
Index……Page 369