Advances in Steiner Trees

✍ Scribed by Jens Albrecht, Dietmar Cieslik (auth.), Ding-Zhu Du, J. M. Smith, J. H. Rubinstein (eds.)

Publisher: Springer US
Year: 2000
Tongue: English
Leaves: 329
Series: Combinatorial Optimization 6
Edition: 1
Category: Library

No coin nor oath required. For personal study only.

✦ Synopsis

The Volume on Advances in Steiner Trees is divided into two sections. The first section of the book includes papers on the general geometric Steiner tree problem in the plane and higher dimensions. The second section of the book includes papers on the Steiner problem on graphs. The general geometric Steiner tree problem assumes that you have a given set of points in some d-dimensional space and you wish to connect the given points with the shortest network possible. The given set ofpoints are 3 Figure 1: Euclidean Steiner Problem in E usually referred to as terminals and the set ofpoints that may be added to reduce the overall length of the network are referred to as Steiner points. What makes the problem difficult is that we do not know a priori the location and cardinality ofthe number ofSteiner points. Thus)the problem on the Euclidean metric is not known to be in NP and has not been shown to be NP-Complete. It is thus a very difficult NP-Hard problem.

✦ Table of Contents

Front Matter....Pages i-xii
The Steiner Ratio of finite-dimensional L p -spaces....Pages 1-13
Shortest Networks for One Line and Two Points in Space....Pages 15-26
Rectilinear Steiner Minimal Trees on Parallel Lines....Pages 27-37
Computing Shortest Networks with Fixed Topologies....Pages 39-62
Steiner Trees, Coordinate Systems and NP-Hardness....Pages 63-80
Exact Algorithms for Plane Steiner Tree Problems: A Computational Study....Pages 81-116
On Approximation of the Power- p and Bottleneck Steiner Trees....Pages 117-135
Exact Steiner Trees in Graphs and Grid Graphs....Pages 137-162
Grade of Service Steiner Trees in Series-Parallel Networks....Pages 163-174
Preprocessing the Steiner Problem in Graphs....Pages 175-233
A Fully Polynomial Approximation Scheme for the Euclidean Steiner Augmentation Problem....Pages 235-253
Effective Local Search Techniques for the Steiner Tree Problem....Pages 255-281
Modern Heuristic Search Methods for the Steiner Tree Problem in Graphs....Pages 283-323

✦ Subjects

Combinatorics; Theory of Computation; Algorithms; Optimization

📜 SIMILAR VOLUMES

Advances in Steiner Trees

📁 Advances in Steiner Trees

✍ J.H. Rubinstein 📂 Library 📅 2000 🏛 Springer 🌐 English

The Steiner ratio of finite-dimensional Lp spaces / J. Albrecht and D. Cieslik -- Shortest networks for one line and two points in space / R. Booth, D.A. Thomas, and J.F. Weng -- Rectilinear Steiner minimal trees on parallel lines / M. Brazil, D. Thomas, and J. Weng -- Computing shortest networks w

Steiner Trees in Industry

📁 Steiner Trees in Industry

✍ Marcus Brazil (auth.), Xiu Zhen Cheng, Ding-Zhu Du (eds.) 📂 Library 📅 2001 🏛 Springer US 🌐 English

The Steiner Tree Problem: A Tour through

📁 The Steiner Tree Problem: A Tour through Graphs, Algorithms, and Complexity (Advanced Lectures in Mathematics)

✍ Hans Jürgen Prömel, Angelika Steger 📂 Library 📅 2002 🏛 Vieweg+Teubner Verlag 🌐 English

In recent years, algorithmic graph theory has become increasingly important as a link between discrete mathematics and theoretical computer science. This textbook introduces students of mathematics and computer science to the interrelated fields of graphs theory, algorithms and complexity.

Steiner tree problems in computer commun

📁 Steiner tree problems in computer communication networks

✍ Dingzhu Du, Xiaodong Hu 📂 Library 📅 2008 🏛 World Scientific 🌐 English

Steiner Minimal Trees

📁 Steiner Minimal Trees

✍ Dietmar Cieslik 📂 Library 📅 1998 🏛 Springer, Berlin 🌐 English

1. Introduction -- 2. SMT and MST in Metric Spaces -- A Survey -- 3. Fermat's Problem in Banach-Minkowski Spaces -- 4. The Degrees of the Vertices in Shortest Trees -- 5. 1-Steiner-Minimal-Trees -- 6. Methods to Construct Shortest Trees -- 7. The Steiner Ratio of Banach-Minkowski Spaces -- 8. Gener

The Steiner Tree Problem

📁 The Steiner Tree Problem

✍ Frank K. Hwang, Dana S. Richards, Pawel Winter 📂 Library 📅 1992 🏛 North-Holland 🌐 English

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 ori