Prömel / Steger The Steiner Tree Problem

A Tour through Graphs, Algorithms, and Complexity
2002
ISBN: 978-3-322-80291-0
Verlag: Vieweg & Teubner
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 241 Seiten, eBook

Reihe: Advanced Lectures in Mathematics

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.

Zielgruppe

Upper undergraduate

Autoren/Hrsg.

Prömel, Hans Jürgen

Steger, Angelika

Inhaltsverzeichnis

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.

Über Autor(innen)

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.