Skip to main content
SpringerLink
Log in
SpringerLink
Log in

Advances in Steiner Trees

  • Book
  • © 2000

Overview

Editors:
  1. Ding-Zhu Du

    1. Department of Computer Science, University of Minnesota, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  2. J. M. Smith

    1. Department of Mechanical & Industrial Engineering, University of Massachusetts, USA

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

  3. J. H. Rubinstein

    1. Department of Mathematics, University of Melbourne, Australia

    View editor publications

    You can also search for this editor in PubMed   Google Scholar

Part of the book series: Combinatorial Optimization (COOP, volume 6)

This is a preview of subscription content, log in via an institution to check access.

Access this book

Log in via an institution
eBook USD 84.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book USD 109.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book USD 109.99
Price excludes VAT (USA)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (13 chapters)

  1. Front Matter

    Pages i-xii
    Download chapter PDF

  2. The Steiner Ratio of finite-dimensional L p -spaces

    • Jens Albrecht, Dietmar Cieslik
    Pages 1-13

  3. Shortest Networks for One Line and Two Points in Space

    • R. S. Booth, D. A. Thomas, J. F. Weng
    Pages 15-26

  4. Rectilinear Steiner Minimal Trees on Parallel Lines

    • Marcus Brazil, Doreen A. Thomas, Jia Feng Weng
    Pages 27-37

  5. Computing Shortest Networks with Fixed Topologies

    • Tao Jiang, Lusheng Wang
    Pages 39-62

  6. Steiner Trees, Coordinate Systems and NP-Hardness

    • J. F. Weng
    Pages 63-80

  7. Exact Algorithms for Plane Steiner Tree Problems: A Computational Study

    • D. M. Warme, P. Winter, M. Zachariasen
    Pages 81-116

  8. On Approximation of the Power-p and Bottleneck Steiner Trees

    • Piotr Berman, Alexander Zelikovsky
    Pages 117-135

  9. Exact Steiner Trees in Graphs and Grid Graphs

    • Siu-Wing Cheng
    Pages 137-162

  10. Grade of Service Steiner Trees in Series-Parallel Networks

    • Charles J. Colbourn, Guoliang Xue
    Pages 163-174

  11. Preprocessing the Steiner Problem in Graphs

    • Cees Duin
    Pages 175-233

  12. A Fully Polynomial Approximation Scheme for the Euclidean Steiner Augmentation Problem

    • J. Scott Provan
    Pages 235-253

  13. Effective Local Search Techniques for the Steiner Tree Problem

    • A. S. C. Wade, V. J. Rayward-Smith
    Pages 255-281

  14. Modern Heuristic Search Methods for the Steiner Tree Problem in Graphs

    • Stefan Voß
    Pages 283-323
Back to top

Keywords

About this book

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.

Editors and Affiliations

  • Department of Computer Science, University of Minnesota, USA

    Ding-Zhu Du

  • Department of Mechanical & Industrial Engineering, University of Massachusetts, USA

    J. M. Smith

  • Department of Mathematics, University of Melbourne, Australia

    J. H. Rubinstein

Bibliographic Information

  • Book Title: Advances in Steiner Trees

  • Editors: Ding-Zhu Du, J. M. Smith, J. H. Rubinstein

  • Series Title: Combinatorial Optimization

  • DOI: https://doi.org/10.1007/978-1-4757-3171-2

  • Publisher: Springer New York, NY

  • eBook Packages: Springer Book Archive

  • Copyright Information: Springer-Verlag US 2000

  • Hardcover ISBN: 978-0-7923-6110-7Published: 31 January 2000

  • Softcover ISBN: 978-1-4419-4824-3Published: 07 December 2010

  • eBook ISBN: 978-1-4757-3171-2Published: 29 June 2013

  • Series ISSN: 1388-3011

  • Edition Number: 1

  • Number of Pages: XII, 323

  • Topics: Combinatorics, Theory of Computation, Algorithms, Optimization

Publish with us

Policies and ethics

Back to top

Search

Navigation