Steiner Tree Problem (eBook)

Front Cover 1
The Steiner Tree Problem 4
Copyright Page 5
Contents 8
Foreword 6
Part I: Euclidean Steiner Problem 14
Chapter 1. Introduction 16
1.1. Historical Background 16
1.2. Some Basic Notions 18
1.3. Some Basic Properties 19
1.4. Full Steiner Trees 21
1.5. Steiner Hulls and Decompositions 22
1.6. The Number of Steiner Topologies 26
1.7 Computational Complexity 27
1.8. Physical Models 29
References 30
Chapter 2. Exact Algorithms 34
2.1. The Melzak Algorithm 35
2.2. A Linear-Time FST Algorithm 36
2.3. Two Ideas on the Melzak Algorithm 38
2.4. A Numerical Algorithm 39
2.5. Pruning 40
2.6. The GEOSTEINER Algorithm 41
2.7. The Negative Edge Algorithm 43
2.8. The Luminary Algorithm 45
References 46
Chapter 3. The Steiner Ratio 50
3.1. Lower Bounds of p 51
3.2. The Small n Case 52
3.3. The Variational Approach 54
3.4. The Steiner Ratio Conjecture as a Maximin Problem 55
3.5. Critical Structures 57
3.6. A Proof of the Steiner Ratio Conjecture 58
References 61
Chapter 4. Heuristics 64
4.1. Minimal Spanning Trees 65
4.2. Improving the MST 65
4.3. Greedy Trees 67
4.4. An Annealing Algorithm 68
4.5. A Partitioning Algorithm 70
4.6. Few’s Algorithms 70
4.7. A Graph Approximation Algorithm 71
4.8. k-Size Quasi-Steiner Trees 72
4.9. Other Heuristics 73
References 73
Chapter 5. Special Terminal-Sets 76
5.1. Four Terminals 76
5.2. Cocircular Terminals 79
5.3. Co-path Terminals 81
5.4. Terminals on Lattice Points 84
5.5. Two Related Results 86
References 88
Chapter 6. Generalizations 90
6.1. d-Dimensional Euclidean Spaces 90
6.2. Cost of Edge 93
6.3. Ternlinal Clusters and New Terminals 96
6.4. k-SMT 97
6.5. Obstacles 98
References 100
Part II: Steiner Problem in Networks 104
Chapter 1. Introduction 106
1.1. Applications 107
1.2. Definitions 108
1.3. Trivial Special Cases 110
1.4. Problem Reformulations 110
1.5. Complexity 113
References 114
Chapter 2. Reductions 116
2.1. Exclusion Tests 117
2.2. Inclusion Tests 125
2.3. Integration of Tests 131
2.4. Effectiveness of Reductions 135
References 136
Chapter 3. Exact Algorithms 138
3.1. Spanning Tree Enumeration Algorithm 138
3.2. Degree-Constrained Tree Enumeration Algorithm 139
3.3. Topology Enumeration Algorithm 140
3.4. Dynamic Programming Algorithm 141
3.5. Branch-and-Bound Algorithm 143
3.6. Mathematical Programming Formulations 145
3.7. Linear Relaxations 150
3.8. Lagrangean Relaxations 151
3.9. Benders’ Decomposition Algorithm 154
3.10. Set Covering Algorithm 156
3.11. Summary and Computational Experience 157
References 160
Chapter 4. Heuristics 164
4.1. Path Heuristics 164
4.2. Tree Heuristics 169
4.3. Vertex Heuristics 177
4.4. Contraction Heuristic 182
4.5. Dual Ascent Heuristic 184
4.6. Set Covering Heuristic 184
4.7. Summary and Computational Experience 185
References 187
Chapter 5. Polynomially Solvable Cases 190
5.1. Series-Parallel Networks 190
5.2. Halin Networks 193
5.3. k-Planar Networks 194
5.4. Strongly Chordal Graphs 198
References 200
Chapter 6. Generalizations 202
6.1. Steiner Trees in Directed Networks 202
6.2. Weighted Steiner Tree Problem 203
6.3. Steiner Forest Problem 204
6.4. Hierarchical Steiner Tree Problem 204
6.5. Degree-Dependent Steiner Tree Problem 205
6.6. Group Steiner Tree Problem 206
6.7. Multiple Steiner Trees Problem 208
6.8. Multiconnected Steiner Network Problem 209
6.9. Steiner Problem in Probabilistic Networks 211
6.10. Realization of Distance Matrices 212
6.11. Other Steiner-Like Problems 212
References 213
Part III: Rectilinear Steiner Problem 216
Chapter 1. Introduction 218
1.1. Definitions 218
1.2. Basic Properties 221
1.3. A Characterization of RSMTs 224
1.4. Problem Reductions 225
1.5. Extremal Results 228
1.6. Computational Complexity 231
1.7. Exact Algorithms 231
References 232
Chapter 2. Heuristic Algoritlinis 234
2.1. Heuristics Using a Given RMST 234
2.2. Heuristics Based on MST Algorithms 242
2.3. Computational Geometry Paradigms 246
2.4. Other Heuristics 250
References 253
Chapter 3. Polynomially Solvable Cases 256
3.1. Terminals on a Rectangular Boundary 256
3.2. Rectilinearly Convex Boundary 264
3.3. Layered Terminal Sets 266
References 267
Chapter 4. Generalizations 270
4.1. Rectangle Trees 270
4.2. Rectilinear Steiner Arborescences 271
4.3. Steiner Trees in Hypercubes 274
4.4. Higher Dimensions 276
References 278
Chapter 5. Routing 280
5.1. Introduction 280
5.2. Heuristics for Single Nets 283
5.3. Heuristics for Multiple Nets 289
5.4. Multiple Layers 293
References 295
Part IV: Other Steiner Problems 298
Chapter 1. Steiner Trees in Other Metric Spaces 300
1.1. Minkowski Spaces 300
1.2. Minkowski Planes and lp Metrics 302
1.3. .-Geometry and Hexagonal Plane 304
1.4. Better Heuristics for Arbitrary Metric Spaces 308
1.5. Bounds for the Performance Ratios of Quasi-STs 310
References 313
Chapter 2. Phylogenetic Trees 314
2.1. Definitions 315
2.2. Compatibility Methods 317
2.3. Maximum Parsimony Methods 319
2.4. Wagner Parsimony Method 321
2.5. Other Maximum Parsimony Methods 326
2.6. Maximum Likelihood Methods 327
2.7. Distance Methods 328
References 331
Subject Index 336
Author Index 348