Advanced Lectures in Mathematics

The Steiner Tree Problem

A Tour through Graphs, Algorithms, and Complexity

Authors: Prömel, Hans Jürgen, Steger, Angelika

Buy this book

eBook $44.99
price for USA (gross)
  • ISBN 978-3-322-80291-0
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Softcover $59.95
price for USA
  • ISBN 978-3-528-06762-5
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
About this Textbook

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. No specific previous knowledge is assumed.
The central theme of the book is a geometrical problem dating back to Jakob Steiner. This problem, now called the Steiner problem, was initially of importance only within the context of land surveying. In the last decade, however, applications as diverse as VLSI-layout and the study of phylogenetic trees led to a rapid rise of interest in this problem. The resulting progress has uncovered fascinating connections between and within graph theory, the study of algorithms, and complexity theory. This single problem thus serves to bind and motivate these areas. The book's topics include: exact algorithms, computational complexity, approximation algorithms, the use of randomness, limits of approximability.
A special feature of the book is that each chapter ends with an "excursion" into some related area. These excursions reinforce the concepts and methods introduced for the Steiner problem by placing them in a broader context.


About the authors

Prof. Dr. Jürgen Prömel ist am Institut für Informatik der Humboldt Universität zu Berlin tätig, Prof. Dr. Angelika Steger lehrt am Institut für Informatik der TU München.

Reviews

"The book is a very good introduction to discrete mathematics in relation to computer science, and a useful reference for those who are interested in network optimization problems." Zentralblatt MATH, Nr. 17/02

"This book is an excellent introduction to the Steiner tree problems, which starts with network Steiner trees an ends with geometric Steiner trees." Mathematical Reviews, Nr. 11/02

Table of contents (10 chapters)

  • Basics I: Graphs

    Prömel, Hans Jürgen (et al.)

    Pages 1-22

  • Basics II: Algorithms

    Prömel, Hans Jürgen (et al.)

    Pages 23-40

  • Basics III: Complexity

    Prömel, Hans Jürgen (et al.)

    Pages 41-62

  • Special Terminal Sets

    Prömel, Hans Jürgen (et al.)

    Pages 63-74

  • Exact Algorithms

    Prömel, Hans Jürgen (et al.)

    Pages 75-86

Buy this book

eBook $44.99
price for USA (gross)
  • ISBN 978-3-322-80291-0
  • Digitally watermarked, DRM-free
  • Included format: PDF
  • ebooks can be used on all reading devices
  • Immediate eBook download after purchase
Softcover $59.95
price for USA
  • ISBN 978-3-528-06762-5
  • Free shipping for individuals worldwide
  • Usually dispatched within 3 to 5 business days.
Loading...

Recommended for you

Loading...

Bibliographic Information

Bibliographic Information
Book Title
The Steiner Tree Problem
Book Subtitle
A Tour through Graphs, Algorithms, and Complexity
Authors
Series Title
Advanced Lectures in Mathematics
Copyright
2002
Publisher
Vieweg+Teubner Verlag
Copyright Holder
Friedr. Vieweg & Sohn Verlagsgesellschaft mbH, Braunschweig/Wiesbaden
eBook ISBN
978-3-322-80291-0
DOI
10.1007/978-3-322-80291-0
Softcover ISBN
978-3-528-06762-5
Series ISSN
0932-7134
Edition Number
1
Number of Pages
VIII, 241
Number of Illustrations and Tables
2 b/w illustrations
Topics