Overview

In recent years, algorithmic graph theory has become increasingly important since it serves as a link between discrete mathematics and theoretical computer science. This textbook introduces students of mathematics and computer science to the interrelated fields of graph 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 tree problem, was initially of importance only within the context of land surveying. Recent applications, as diverse as VLSI-layout and the study of phylogenetic trees, have, however, lead to significant interest in the problem. The resulting progress has uncovered fascinating connections to and among graph theory, the study of algorithms and complexity. The single problem thus serves to bind and motivate these areas. The book's topics include: exact algorithms; computational complexity; approximation algorithms; limits of approximability; randomness helps; the Manhattan Steiner problem; heuristics; packing of Steiner trees; and applications. A fundamental 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 tree problem by putting them in a broader context.

Full Product Details

Author:   Hans Jürgen Prömel ,  Angelika Steger ,  Martin Aigner ,  Hans-Juergen Proemel
Publisher:   Springer Fachmedien Wiesbaden
Imprint:   Vieweg+Teubner Verlag
Edition:   Softcover reprint of the original 1st ed. 2002
Dimensions:   Width: 17.00cm , Height: 1.30cm , Length: 24.00cm
Weight:   0.441kg
ISBN:  

9783528067625

ISBN 10:   3528067624
Pages:   241
Publication Date:   25 February 2002
Audience:   College/higher education ,  Undergraduate ,  Postgraduate, Research & Scholarly
Format:   Paperback
Publisher's Status:   Active
Availability:   In Print  
This item will be ordered in for you from one of our suppliers. Upon receipt, we will promptly dispatch it out to you. For in store availability, please contact us.
Language:   English

Table of Contents

1 Basics I: Graphs.- 1.1 Introduction to graph theory.- 1.2 Excursion: Random graphs.- 2 Basics II: Algorithms.- 2.1 Introduction to algorithms.- 2.2 Excursion: Fibonacci heaps and amortized time.- 3 Basics III: Complexity.- 3.1 Introduction to complexity theory.- 3.2 Excursion: More NP-complete problems.- 4 Special Terminal Sets.- 4.1 The shortest path problem.- 4.2 The minimum spanning tree problem.- 4.3 Excursion: Matroids and the greedy algorithm.- 5 Exact Algorithms.- 5.1 The enumeration algorithm.- 5.2 The Dreyfus-Wagner algorithm.- 5.3 Excursion: Dynamic programming.- 6 Approximation Algorithms.- 6.1 A simple algorithm with performance ratio 2.- 6.2 Improving the time complexity.- 6.3 Excursion: Machine scheduling.- 7 More on Approximation Algorithms.- 7.1 Minimum spanning trees in hypergraphs.- 7.2 Improving the performance ratio I.- 7.3 Excursion: The complexity of optimization problems.- 8 Randomness Helps.- 8.1 Probabilistic complexity classes.- 8.2 Improving the performance ratio II.- 8.3 An almost always optimal algorithm.- 8.4 Excursion: Primality and cryptography.- 9 Limits of Approximability.- 9.1 Reducing optimization problems.- 9.2 APX-completeness.- 9.3 Excursion: Probabilistically checkable proofs.- 10 Geometric Steiner Problems.- 10.1 A characterization of rectilinear Steiner minimum trees.- 10.2 The Steiner ratios.- 10.3 An almost linear time approximation scheme.- 10.4 Excursion: The Euclidean Steiner problem.- Symbol Index.

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"

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

Author Information

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.

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions