The Steiner Tree Problem A Tour through Graphs, Algorithms, and Comp
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
- PDF / 38,433,149 Bytes
- 251 Pages / 482 x 680 pts Page_size
- 97 Downloads / 179 Views
The Steiner Tree Problem
Advanced Lectures in Mathematics
Editorial board: Prof. Dr. Martin Aigner, Freie Universitiit Berlin, Germany Prof. Dr. Peter Gritzmann, Technische UniversWit Munchen, Germany Prof. Dr. Volker Mehrmann, Technische Universitiit Berlin, Germany Prof. Dr. Gisbert Wustholz, ETH Zurich, Switzerland
Introduction to Markov Chains Ehrhard Behrends Einfiihrung in die Symplektische Geometrie Rolf Berndt Wavelets - Eine Einfiihrung Christian Blatter Local Analytic Geometry Theo de Jong, Gerhard Pfister Ruled Varieties Gerd Fischer, Jens Piontkowski Dirac-Operatoren in der Riemannschen Geometrie Thomas Friedrich Hypergeometric Summation Wolfram Koepf The Steiner Tree Problem Hans Jiirgen Promel, Angelika Steger The Basic Theory of Power Series Jesus M. Ruiz
vieweg ___________________''
Hans Jiirgen Promel Angelika Steger
The Steiner Tree Problem A Tour through Graphs, Algorithms, and Complexity
~
vleweg
Prof. Dr. Hans Jiirgen Promei Humboldt Universitiit zu Berlin Institut flir Informatik Unter den Linden 6 10099 Berlin, Germany
Prof. Dr. Angelika Steger Technische Universitat Miinchen Institut flir Informatik 80290 Miinchen, Germany [email protected]
[email protected]
Mathematics Subject Classification 05Cxx Graph theory 68Qxx Theory of computing 68Rxx Discrete mathematics in relation to computer science 68Wxx Algorithms
Die Deutsche Bibliothek - CIP-Cataloguing-in-Publication-Data A catalogue record for this publication is available from Die Deutsche Bibliothek.
First edition, February 2002
All rights reserved © Friedr. Vieweg & Sohn Verlagsgesellschaft mbH, BraunschweiglWiesbaden, 2002 Vieweg is a company in the specialist publishing group BertelsmannSpringer. www.vieweg.de
No part of this publication may be reproduced, stored in a retrieval system or transmitted, mechanical, photocopying or otherwise without prior permission of the copyright holder.
Cover design: Ulrike Weigel, www.CorporateDesignGroup.de Printed on acid-free paper ISBN-13: 978-3-528-06762-5 DOl: 10.1007/978-3-322-80291-0
e-ISBN-13: 978-3-322-80291-0
Preface
"A very simple but instructive problem was treated by Jacob Steiner, the famous representative of geometry at the University of Berlin in the early nineteenth century. Three villages A,B ,C are to be joined by a system of roads of minimum length." Due to this remark of Courant and Robbins (1941), a problem received its name that actually reaches two hundred years further back and should more appropriately be attributed to the French mathematician Pierre Fermat. At the end of his famous treatise "Minima and Maxima" he raised the question to find for three given points in the plane a fourth one in such a way that the sum of its distances to the given points is minimized - that is, to solve the problem mentioned above in its mathematical abstraction. It is known that Evangelista Torricelli had found a geometrical solution for this problem already before 1640. During the last centuries this problem was rediscovered and generalized by many mathem
