# The Steiner Tree Problem, Volume 53

## 1st Edition

**Authors:**F.K. Hwang D.S. Richards P. Winter

**Hardcover ISBN:**9780444890986

**eBook ISBN:**9780080867939

**Imprint:**North Holland

**Published Date:**20th October 1992

**Page Count:**336

**View all volumes in this series:**Annals of Discrete Mathematics

## Table of Contents

**Euclidean Steiner Problem.** Introduction. *Historical Background. Some Basic Notions. Some Basic Properties. Full Steiner Trees. Steiner Hulls and Decompositions. The Number of Steiner Topologies. Computational Complexity. Physical Models. References.* Exact Algorithms. *The Melzak Algorithm. A Linear-Time FST Algorithm. Two Ideas on the Melzak Algorithm. A Numerical Algorithm. Pruning. The GEOSTEINER Algorithm. The Negative Edge Algorithm. The Luminary Algorithm. References.* The Steiner Ratio.* Lower Bounds of &rgr;. The Small n Case. The Variational Approach. The Steiner Ratio Conjecture as a Maximin Problem. Critical Structures. A Proof of the Steiner Ratio Conjecture. References.* Heuristics.* Minimal Spanning Trees. Improving the MST. Greedy Trees. An Annealing Algorithm. A Partitioning Algorithm. Few's Algorithms. A Graph Approximation Algorithm. k-Size Quasi-Steiner Trees. Other Heuristics. References.* Special Terminal-Sets.* Four Terminals. Cocircular Terminals. Co-path Terminals. Terminals on Lattice Points. Two Related Results. References.* Generalizations.* d-Dimensional Euclidean Spaces. Cost of Edge. Terminal Clusters and New Terminals. k-SMT. Obstacles. References.* **Steiner Problem in Networks.** Introduction.* Applications. Definitions. Trivial Special Cases. Problem Reformulations. Complexity. References.* Reductions.* Exclusion Tests. Inclusion Tests. Integration of Tests. Effectiveness of Reductions. References.* Exact Algorithms.* Spanning Tree Enumeration Algorithm. Degree-Constrained Tree Enumeration Algorithm. Topology Enumeration Algorithm. Dynamic Programming Algorithm. Branch-and-Bound Algorithm. Mathematical Programming Formulations. Linear Relaxations. Lagrangean Relaxations. Benders' Decomposition Algorithm. Set Covering Algorithm. Summary and Computational Experience. References.* Heuristics.* Path Heurisitics. Tree Heuristics. Vertex Heuristics. Contraction Heuristic. Dual Ascent Heuristic. Set Covering Heuristic. Summary and Computational Experience. References.* Polynomially Solvable Cases.* Series-Parallel Networks. Halin Networks. k-Planar Networks. Strongly Chordal Graphs. References.* Generalizations.* Steiner Trees in Directed Networks. Weighted Steiner Tree Problem. Steiner Forest Problem. Hierarchical Steiner Tree Problem. Degree-Dependent Steiner Tree Problem. Group Steiner Tree Problem. Multiple Steiner Trees Problem. Multiconnected Steiner Network Problem. Steiner Problem in Probabilistic Networks. Realization of Distance Matrices. Other Steiner-Like Problems. References.* **Rectilinear Steiner Problem.** Introduction.* Definitions. Basic Properties. A Characterization of RSMTs. Problem Reductions. Extremal Results. Computational Complexity. Exact Algorithms. References.* Heuristic Algorithms.* Heuristics Using a Given RMST. Heuristics Based on MST Algorithms. Computational Geometry Paradigms. Other Heuristics. References.* Polynomially Solvable Cases.* Terminals on a Rectangular Boundary. Rectilinearly Convex Boundary. Layered Terminal Sets. References.* Generalizations.* Rectangle Trees. Rectilinear Steiner Arborescences. Steiner Trees in Hypercubes. Higher Dimensions. References.* Routing. * Introduction. Heuristics for Single Nets. Heuristics for Multiple Nets. Multiple Layers. References.* **Other Steiner Problems.** Steiner Trees in Other Metric Spaces.* Minkowski Spaces. Minkowski Planes and lp Metrics. &lgr;-Geometry and Hexagonal Plane. Better Heuristics for Arbitrary Metric Spaces. Bounds for the Performance Ratios of Quasi-STs. References.* Phylogenetic Trees.* Definitions. Compatibility Methods. Maximum Parsimony Methods. Wagner Parsimony Method. Other Maximum Parsimony Methods. Maximum Likelihood Methods. Distance Methods. References.*Subject Index. Author Index.

## Description

**Euclidean Steiner Problem.** Introduction. *Historical Background. Some Basic Notions. Some Basic Properties. Full Steiner Trees. Steiner Hulls and Decompositions. The Number of Steiner Topologies. Computational Complexity. Physical Models. References.* Exact Algorithms. *The Melzak Algorithm. A Linear-Time FST Algorithm. Two Ideas on the Melzak Algorithm. A Numerical Algorithm. Pruning. The GEOSTEINER Algorithm. The Negative Edge Algorithm. The Luminary Algorithm. References.* The Steiner Ratio.* Lower Bounds of &rgr;. The Small n Case. The Variational Approach. The Steiner Ratio Conjecture as a Maximin Problem. Critical Structures. A Proof of the Steiner Ratio Conjecture. References.* Heuristics.* Minimal Spanning Trees. Improving the MST. Greedy Trees. An Annealing Algorithm. A Partitioning Algorithm. Few's Algorithms. A Graph Approximation Algorithm. k-Size Quasi-Steiner Trees. Other Heuristics. References.* Special Terminal-Sets.* Four Terminals. Cocircular Terminals. Co-path Terminals. Terminals on Lattice Points. Two Related Results. References.* Generalizations.* d-Dimensional Euclidean Spaces. Cost of Edge. Terminal Clusters and New Terminals. k-SMT. Obstacles. References.* **Steiner Problem in Networks.** Introduction.* Applications. Definitions. Trivial Special Cases. Problem Reformulations. Complexity. References.* Reductions.* Exclusion Tests. Inclusion Tests. Integration of Tests. Effectiveness of Reductions. References.* Exact Algorithms.* Spanning Tree Enumeration Algorithm. Degree-Constrained Tree Enumeration Algorithm. Topology Enumeration Algorithm. Dynamic Programming Algorithm. Branch-and-Bound Algorithm. Mathematical Programming Formulations. Linear Relaxations. Lagrangean Relaxations. Benders' Decomposition Algorithm. Set Covering Algorithm. Summary and Computational Experience. References.* Heuristics.* Path Heurisitics. Tree Heuristics. Vertex Heuristics. Contraction Heuristic. Dual Ascent Heuristic. Set Covering Heuristic. Summary and Computational Experience. References.* Polynomially Solvable Cases.* Series-Parallel Networks. Halin Networks. k-Planar Networks. Strongly Chordal Graphs. References.* Generalizations.* Steiner Trees in Directed Networks. Weighted Steiner Tree Problem. Steiner Forest Problem. Hierarchical Steiner Tree Problem. Degree-Dependent Steiner Tree Problem. Group Steiner Tree Problem. Multiple Steiner Trees Problem. Multiconnected Steiner Network Problem. Steiner Problem in Probabilistic Networks. Realization of Distance Matrices. Other Steiner-Like Problems. References.* **Rectilinear Steiner Problem.** Introduction.* Definitions. Basic Properties. A Characterization of RSMTs. Problem Reductions. Extremal Results. Computational Complexity. Exact Algorithms. References.* Heuristic Algorithms.* Heuristics Using a Given RMST. Heuristics Based on MST Algorithms. Computational Geometry Paradigms. Other Heuristics. References.* Polynomially Solvable Cases.* Terminals on a Rectangular Boundary. Rectilinearly Convex Boundary. Layered Terminal Sets. References.* Generalizations.* Rectangle Trees. Rectilinear Steiner Arborescences. Steiner Trees in Hypercubes. Higher Dimensions. References.* Routing. * Introduction. Heuristics for Single Nets. Heuristics for Multiple Nets. Multiple Layers. References.* **Other Steiner Problems.** Steiner Trees in Other Metric Spaces.* Minkowski Spaces. Minkowski Planes and lp Metrics. &lgr;-Geometry and Hexagonal Plane. Better Heuristics for Arbitrary Metric Spaces. Bounds for the Performance Ratios of Quasi-STs. References.* Phylogenetic Trees.* Definitions. Compatibility Methods. Maximum Parsimony Methods. Wagner Parsimony Method. Other Maximum Parsimony Methods. Maximum Likelihood Methods. Distance Methods. References.*Subject Index. Author Index.

## Details

- No. of pages:
- 336

- Language:
- English

- Copyright:
- © North Holland 1992

- Published:
- 20th October 1992

- Imprint:
- North Holland

- eBook ISBN:
- 9780080867939

## About the Authors

### F.K. Hwang Author

### Affiliations and Expertise

AT&T Bell Laboratories, Murray Hill, NJ, USA

### D.S. Richards Author

### Affiliations and Expertise

University of Virginia, Thornton Hall, VA, USA

### P. Winter Author

### Affiliations and Expertise

University of Copenhagen, Copenhagen, Denmark