## ＜電子ブック＞The Steiner Tree Problem : A Tour through Graphs, Algorithms, and Complexity

責任表示 by Hans Jürgen Prömel, Angelika Steger Prömel, Hans Jürgen Steger, Angelika SpringerLink (Online service) English (英語) Vieweg+Teubner Verlag 2002- Wiesbaden, Germany シリーズ 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 an...d 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.続きを見る 1 Basics I: Graphs1.1 Introduction to graph theory1.2 Excursion: Random graphs2 Basics II: Algorithms2.1 Introduction to algorithms2.2 Excursion: Fibonacci heaps and amortized time3 Basics III: Complexity3.1 Introduction to complexity theory3.2 Excursion: More NP-complete problems4 Special Terminal Sets4.1 The shortest path problem4.2 The minimum spanning tree problem4.3 Excursion: Matroids and the greedy algorithm5 Exact Algorithms5.1 The enumeration algorithm5.2 The Dreyfus-Wagner algorithm5.3 Excursion: Dynamic programming6 Approximation Algorithms6.1 A simple algorithm with performance ratio 26.2 Improving the time complexity6.3 Excursion: Machine scheduling7 More on Approximation Algorithms7.1 Minimum spanning trees in hypergraphs7.2 Improving the performance ratio I7.3 Excursion: The complexity of optimization problems8 Randomness Helps8.1 Probabilistic complexity classes8.2 Improving the performance ratio II8.3 An almost always optimal algorithm8.4 Excursion: Primality and cryptography9 Limits of Approximability9.1 Reducing optimization problems9.2 APX-completeness9.3 Excursion: Probabilistically checkable proofs10 Geometric Steiner Problems10.1 A characterization of rectilinear Steiner minimum trees10.2 The Steiner ratios10.3 An almost linear time approximation scheme10.4 Excursion: The Euclidean Steiner problemSymbol Index.続きを見る http://hdl.handle.net/2324/1001400427 Full text available from SpringerLink ebooks - Mathematics and Statistics (Archive)

### 詳細

レコードID 3645434 QA401-425 511.4 Mathematics. Algebra. Mathematics. Approximations and Expansions. Algebra. ssj0001298571 9783528067625(print) 9783322802910 2020.06.27 2020.06.28