UID:
edoccha_9958094986202883
Format:
1 online resource (353 p.)
ISBN:
1-281-78968-2
,
9786611789688
,
0-08-086793-6
Series Statement:
Annals of discrete mathematics ; 53
Content:
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
Note:
Description based upon print version of record.
,
Front Cover; The Steiner Tree Problem; Copyright Page; Contents; Foreword; Part I: Euclidean Steiner Problem; Chapter 1. Introduction; 1.1. Historical Background; 1.2. Some Basic Notions; 1.3. Some Basic Properties; 1.4. Full Steiner Trees; 1.5. Steiner Hulls and Decompositions; 1.6. The Number of Steiner Topologies; 1.7 Computational Complexity; 1.8. Physical Models; References; Chapter 2. Exact Algorithms; 2.1. The Melzak Algorithm; 2.2. A Linear-Time FST Algorithm; 2.3. Two Ideas on the Melzak Algorithm; 2.4. A Numerical Algorithm; 2.5. Pruning; 2.6. The GEOSTEINER Algorithm
,
2.7. The Negative Edge Algorithm2.8. The Luminary Algorithm; References; Chapter 3. The Steiner Ratio; 3.1. Lower Bounds of p; 3.2. The Small n Case; 3.3. The Variational Approach; 3.4. The Steiner Ratio Conjecture as a Maximin Problem; 3.5. Critical Structures; 3.6. A Proof of the Steiner Ratio Conjecture; References; Chapter 4. Heuristics; 4.1. Minimal Spanning Trees; 4.2. Improving the MST; 4.3. Greedy Trees; 4.4. An Annealing Algorithm; 4.5. A Partitioning Algorithm; 4.6. Few's Algorithms; 4.7. A Graph Approximation Algorithm; 4.8. k-Size Quasi-Steiner Trees; 4.9. Other Heuristics
,
ReferencesChapter 5. Special Terminal-Sets; 5.1. Four Terminals; 5.2. Cocircular Terminals; 5.3. Co-path Terminals; 5.4. Terminals on Lattice Points; 5.5. Two Related Results; References; Chapter 6. Generalizations; 6.1. d-Dimensional Euclidean Spaces; 6.2. Cost of Edge; 6.3. Ternlinal Clusters and New Terminals; 6.4. k-SMT; 6.5. Obstacles; References; Part II: Steiner Problem in Networks; Chapter 1. Introduction; 1.1. Applications; 1.2. Definitions; 1.3. Trivial Special Cases; 1.4. Problem Reformulations; 1.5. Complexity; References; Chapter 2. Reductions; 2.1. Exclusion Tests
,
2.2. Inclusion Tests2.3. Integration of Tests; 2.4. Effectiveness of Reductions; References; Chapter 3. Exact Algorithms; 3.1. Spanning Tree Enumeration Algorithm; 3.2. Degree-Constrained Tree Enumeration Algorithm; 3.3. Topology Enumeration Algorithm; 3.4. Dynamic Programming Algorithm; 3.5. Branch-and-Bound Algorithm; 3.6. Mathematical Programming Formulations; 3.7. Linear Relaxations; 3.8. Lagrangean Relaxations; 3.9. Benders' Decomposition Algorithm; 3.10. Set Covering Algorithm; 3.11. Summary and Computational Experience; References; Chapter 4. Heuristics; 4.1. Path Heuristics
,
4.2. Tree Heuristics4.3. Vertex Heuristics; 4.4. Contraction Heuristic; 4.5. Dual Ascent Heuristic; 4.6. Set Covering Heuristic; 4.7. Summary and Computational Experience; References; Chapter 5. Polynomially Solvable Cases; 5.1. Series-Parallel Networks; 5.2. Halin Networks; 5.3. k-Planar Networks; 5.4. Strongly Chordal Graphs; References; Chapter 6. Generalizations; 6.1. Steiner Trees in Directed Networks; 6.2. Weighted Steiner Tree Problem; 6.3. Steiner Forest Problem; 6.4. Hierarchical Steiner Tree Problem; 6.5. Degree-Dependent Steiner Tree Problem; 6.6. Group Steiner Tree Problem
,
6.7. Multiple Steiner Trees Problem
,
English
Additional Edition:
ISBN 0-444-89098-X
Language:
English
