The Steiner Tree Problem

by Hwang, Frank K.; Richards, Dana S.; Winter, Pawel

• ISBN13: 9780444890986
• ISBN10: 044489098X
• Format: Hardcover
• Copyright: 1992-09-01
• Publisher: Elsevier Science Ltd

Summary

The Steiner problem asks for a shortest network which spans a given set of points. Minimum spanning networks have been well-studied when all connections are required to be between the given points. The novelty of the Steiner tree problem is that new auxiliary points can be introduced between the original points so that a spanning network of all the points will be shorter than otherwise possible. These new points are called Steiner points - locating them has proved problematic and research has diverged along many different avenues.This volume is devoted to the assimilation of the rich field of intriguing analyses and the consolidation of the fragments. A section has been given to each of the three major areas of interest which have emerged. The first concerns the Euclidean Steiner Problem, historically the original Steiner tree problem proposed by Jarniacute;k and Kouml;ssler in 1934. The second deals with the Steiner Problem in Networks, which was propounded independently by Hakimi and Levin and has enjoyed the most prolific research amongst the three areas. The Rectilinear Steiner Problem, introduced by Hanan in 1965, is discussed in the third part. Additionally, a forth section has been included, with chapters discussing areas where the body of results is still emerging.The collaboration of three authors with different styles and outlooks affords individual insights within a cohesive whole.

Table of Contents

Foreword
Euclidean Steiner Problem	p. 1
Introduction	p. 3
Historical Background	p. 3
Some Basic Notions	p. 5
Some Basic Properties	p. 6
Full Steiner Trees	p. 8
Steiner Hulls and Decompositions	p. 9
The Number of Steiner Topologies	p. 13
Computational Complexity	p. 14
Physical Models	p. 16
Exact Algorithms	p. 21
The Melzak Algorithm	p. 22
A Linear-Time FST Algorithm	p. 23
Two Ideas on the Melzak Algorithm	p. 25
A Numerical Algorithm	p. 26
Pruning	p. 27
The GEOSTEINER Algorithm	p. 28
The Negative Edge Algorithm	p. 30
The Luminary Algorithm	p. 32
The Steiner Ratio	p. 37
Lower Bounds of [rho]	p. 38
The Small n Case	p. 39
The Variational Approach	p. 41
The Steiner Ratio Conjecture as a Maximin Problem	p. 42
Critical Structures	p. 44
A Proof of the Steiner Ratio Conjecture	p. 45
Heuristics	p. 51
Minimal Spanning Trees	p. 52
Improving the FIST	p. 52
Greedy Trees	p. 54
An Annealing Algorithm	p. 55
A Partitioning Algorithm	p. 57
Few's Algorithms	p. 57
A Graph Approximation Algorithm	p. 58
k-Size Quasi-Steiner Trees	p. 59
Other Heuristics	p. 60
Special Terminal-Sets	p. 63
Four Terminals	p. 63
Cocircular Terminals	p. 66
Co-path Terminals	p. 68
Terminals on Lattice Points	p. 71
Two Related Results	p. 73
Generalizations	p. 77
d-Dimensional Euclidean Spaces	p. 77
Cost of Edge	p. 80
Terminal Clusters and New Terminals	p. 83
k-SMT	p. 84
Obstacles	p. 85
Steiner Problem in Networks	p. 91
Introduction	p. 93
Applications	p. 94
Definitions	p. 95
Trivial Special Cases	p. 97
Problem Reformulations	p. 97
Complexity	p. 100
Reductions	p. 103
Exclusion Tests	p. 104
Inclusion Tests	p. 112
Integration of Tests	p. 118
Effectiveness of Reductions	p. 122
Exact Algorithms	p. 125
Spanning Tree Enumeration Algorithm	p. 125
Degree-Constrained Tree Enumeration Algorithm	p. 126
Topology Enumeration Algorithm	p. 127
Dynamic Programming Algorithm	p. 128
Branch-and-Bound Algorithm	p. 130
Mathematical Programming Formulations	p. 132
Linear Relaxations	p. 137
Lagrangean Relaxations	p. 138
Benders' Decomposition Algorithm	p. 141
Set Covering Algorithm	p. 143
Summary and Computational Experience	p. 144
Heuristics	p. 151
Path Heuristics	p. 151
Tree Heuristics	p. 156
Vertex Heuristics	p. 164
Contraction Heuristic	p. 169
Dual Ascent Heuristic	p. 171
Set Covering Heuristic	p. 171
Summary and Computational Experience	p. 172
Polynomially Solvable Cases	p. 177
Series-Parallel Networks	p. 177
Halin Networks	p. 180
k-Planar Networks	p. 181
Strongly Chordal Graphs	p. 185
Generalizations	p. 189
Steiner Trees in Directed Networks	p. 189
Weighted Steiner Tree Problem	p. 190
Steiner Forest Problem	p. 191
Hierarchical Steiner Tree Problem	p. 191
Degree-Dependent Steiner Tree Problem	p. 192
Group Steiner Tree Problem	p. 193
Multiple Steiner Trees Problem	p. 195
Multiconnected Steiner Network Problem	p. 196
Steiner Problem in Probabilistic Networks	p. 198
Realization of Distance Matrices	p. 199
Other Steiner-Like Problems	p. 199
Rectilinear Steiner Problem	p. 203
Introduction	p. 205
Definitions	p. 205
Basic Properties	p. 208
A Characterization of RSMTs	p. 211
Problem Reductions	p. 212
Extremal Results	p. 215
Computational Complexity	p. 218
Exact Algorithm	p. 218
Heuristic Algorithms	p. 221
Heuristics Using a Given RMST	p. 221
Heuristics Based on MST Algorithms	p. 229
Computational Geometry Paradigms	p. 233
Other Heuristics	p. 237
Polynomially Solvable Cases	p. 243
Terminals on a Rectangular Boundary	p. 243
Rectilinearly Convex Boundary	p. 251
Layered Terminal Sets	p. 253
Generalizations	p. 257
Rectangle Trees	p. 257
Rectilinear Steiner Arborescences	p. 258
Steiner Trees in Hypercubes	p. 261
Higher Dimensions	p. 263
Routing	p. 267
Introduction	p. 267
Heuristics for Single Nets	p. 270
Heuristics for Multiple Nets	p. 276
Multiple Layers	p. 280
Other Steiner Problems	p. 285
Steiner Trees in Other Metric Spaces	p. 287
Minkowski Spaces	p. 287
Minkowski Planes and l[subscript p] Metrics	p. 289
[lambda]-Geometry and Hexagonal Plane	p. 291
Better Heuristics for Arbitrary Metric Spaces	p. 295
Bounds for the Performance Ratios of Quasi-STs	p. 297
Phylogenetic Trees	p. 301
Definitions	p. 302
Compatibility Methods	p. 304
Maximum Parsimony Methods	p. 306
Wagner Parsimony Method	p. 308
Other Maximum Parsimony Methods	p. 313
Maximum Likelihood Methods	p. 314
Distance Methods	p. 315
Subject Index	p. 323
Author Index	p. 335
Table of Contents provided by Blackwell. All Rights Reserved.