Author | Prรถmel, Hans Jรผrgen. author |
---|---|
Title | The Steiner Tree Problem [electronic resource] : A Tour through Graphs, Algorithms, and Complexity / by Hans Jรผrgen Prรถmel, Angelika Steger |
Imprint | Wiesbaden : Vieweg+Teubner Verlag, 2002 |
Connect to | http://dx.doi.org/10.1007/978-3-322-80291-0 |
Descript | VIII, 241 p. 2 illus. online resource |
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