Contents -- Preface -- Part I. Fundamentals of Classical Steiner Tree Problem -- 1. Minimax Approach and Steiner Ratio -- 1.1 Minimax Approach -- 1.1.1 Chebyshev Theorem -- 1.1.2 Du-Hwang Theorem -- 1.1.3 Geometric Inequalities -- 1.1.4 Analysis of Approximation Performance -- 1.2 Steiner Ratio in the Euclidean Plane -- 1.2.1 Equivalent Minimax Problem -- 1.2.2 Characteristic Area -- 1.2.3 Inner Spanning Trees -- 1.2.4 Critical Structure -- 1.2.5 Hexagonal Trees -- 1.3 Steiner Ratios in Other Metric Spaces -- 1.3.1 Steiner Ratios in Euclidean Spaces -- 1.3.2 Steiner Ratio in Rectilinear Spaces -- 1.3.3 Steiner Ratio in Banach Spaces -- 1.4 Discussions -- 2. k-Steiner Ratios and Better Approximation Algorithms -- 2.1 k-Steiner Ratio -- 2.1.1 Upper Bound for k-Steiner Ratio -- 2.1.2 Lower Bound for k-Steiner Ratio -- 2.2 Approximations Better Than Minimum Spanning Tree -- 2.2.1 Greedy Strategy -- 2.2.2 Variable Metric Method -- 2.2.3 Relative Greedy Strategy -- 2.2.4 Preprocessing Technique -- 2.2.5 Loss-Contracting Algorithm -- 2.3 Discussions -- 3. Geometric Partitions and Polynomial Time Approximation Schemes -- 3.1 Guillotine Cut for Rectangular Partition -- 3.1.1 1-Guillotine Cut -- 3.1.2 m-Guillotine Cut -- 3.1.3 Guillotine Cut for Rectilinear Steiner Minimum Tree -- 3.2 Portals -- 3.2.1 Portals for Rectilinear Steiner Minimum Tree -- 3.2.2 Portals versus Guillotine Cuts -- 3.2.3 Portals Integrated with Guillotine Cuts -- 3.2.4 Two-Stage Portals -- 3.3 Banyan and Spanner -- 3.4 Discussions -- 4. Grade of Service Steiner Tree Problem -- 4.1 GoSST Problem in the Euclidean Plane -- 4.1.1 Recursive Approximation Algorithm -- 4.1.2 Branch-and-Bound Algorithm -- 4.2 Minimum GoSST Problem in Graphs -- 4.2.1 -Convex -Approximation Steiner Tree Algorithms -- 4.2.2 Algorithm for Two Non-Zero Rates -- 4.2.3 Algorithm for Arbitrary Number of Rates.

4.3 Discussions -- 5. Steiner Tree Problem for Minimal Steiner Points -- 5.1 In the Euclidean Plane -- 5.1.1 Complexity Study -- 5.1.2 Steinerized Minimum Spanning Tree Algorithm -- 5.1.3 Greedy Algorithm -- 5.1.4 Polynomial Time Approximation Scheme -- 5.1.4.1 Partition Strategy -- 5.1.4.2 Approximation Scheme -- 5.1.4.3 Exact Algorithm -- 5.1.4.4 Connecting Local Forests and Boundary Points -- 5.2 In the Rectilinear Plane -- 5.2.1 Steinerized Minimum Spanning Tree Algorithm -- 5.2.2 Greedy Algorithm -- 5.3 In Metric Spaces -- 5.4 Discussions -- 6. Bottleneck Steiner Tree Problem -- 6.1 Complexity Study -- 6.2 Steinerized Minimum Spanning Tree Algorithm -- 6.3 3-Restricted Steiner Tree Algorithm -- 6.4 Discussions -- 7. Steiner k-Tree and k-Path Routing Problems -- 7.1 Problem Formulation and Complexity Study -- 7.1.1 Problem Formulation -- 7.1.2 Complexity Study -- 7.2 Algorithms for k-Path Routing Problem -- 7.2.1 Steiner Tree Based Algorithm -- 7.2.2 Set Cover Based Algorithm -- 7.3 Algorithms for k-Tree Routing Problem -- 7.3.1 Hamilton Circuit Based Algorithm -- 7.3.2 Steiner Tree Based Algorithm -- 7.4 Discussions -- 8. Steiner Tree Coloring Problem -- 8.1 Maximum Tree Coloring -- 8.1.1 Problem Formulation -- 8.1.2 Inapproximability Analysis -- 8.1.3 Approximation Algorithms -- 8.1.3.1 For General Graphs -- 8.1.3.2 For Special Graphs -- 8.2 Minimum Tree Coloring -- 8.2.1 Problem Formulation -- 8.2.2 Inapproximability Analysis -- 8.2.3 Approximation Algorithms -- 8.2.3.1 For General Graphs -- 8.2.3.2 For Special graphs -- 8.3 Discussions -- 9. Steiner Tree Scheduling Problem -- 9.1 Minimum Aggregation Time -- 9.1.1 Problem Formulation -- 9.1.2 Complexity Analysis -- 9.1.3 Greedy Algorithms -- 9.1.3.1 Basic Algorithm -- 9.1.3.2 Algorithms for Special Cases -- 9.1.4 Partition Algorithm -- 9.1.4.1 Aggregation Tree Construction.

9.1.4.2 Aggregation Time Schedule -- 9.1.5 Performance Analysis of Algorithm -- 9.2 Minimum Multicast Time Problem -- 9.2.1 Problem Formulation -- 9.2.2 Complexity Study -- 9.2.3 Approximation Algorithm -- 9.2.4 Performance Analysis of Algorithm -- 9.3 Discussions -- 9.3.1 Convergecast -- 9.3.2 Multicast -- 9.3.3 Convergecast and Multicast -- 10. Survivable Steiner Network Problem -- 10.1 Minimum k-Connected Steiner Networks -- 10.1.1 Minimum Strong k-Connected Steiner Networks -- 10.1.2 Minimum Weak k-Connected Steiner Networks -- 10.2 Minimum Weak Two-Connected Steiner Networks -- 10.2.1 Complexity Study -- 10.2.2 Generalized Steiner Ratio -- 10.2.3 In the Rectilinear Plane -- 10.3 Minimum Weak Three-Edge-Connected Steiner Networks -- 10.3.1 In the Euclidean Plane -- 10.3.2 In the Rectilinear Plane -- 10.4 Discussions -- 10.4.1 Minimally k-Edge Connected Networks -- 10.4.2 Minimum k-Edge Connected Spanning Networks -- 10.4.3 Minimum k-Vertex Connected Spanning Networks -- 10.4.4 Minimum Spanning Network of Nonuniform Connectivity -- Appendix A More Steiner Tree Related Problems -- Bibliography -- Index.