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
72.95 + applicable tax
43.99 + applicable tax
54.95 + applicable tax
Unavailable
Compatible Not compatible
VitalSource PC, Mac, iPhone & iPad Amazon Kindle eReader
ePub & PDF Apple & PC desktop. Mobile devices (Apple & Android) Amazon Kindle eReader
Mobi Amazon Kindle eReader Anything else

Institutional Access


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 Heuri

Description

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 Jarník and Kö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.


Details

No. of pages:
336
Language:
English
Copyright:
© North Holland 1992
Published:
Imprint:
North Holland
eBook ISBN:
9780080867939
Hardcover ISBN:
9780444890986

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