<電子ブック>
The Steiner Tree Problem : A Tour through Graphs, Algorithms, and Complexity

責任表示
著者
本文言語
出版者
出版年
出版地
関連情報
概要 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: 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.
続きを見る
冊子版へのリンク
本文を見る Full text available from SpringerLink ebooks - Mathematics and Statistics (Archive)

詳細

レコードID
主題
SSID
eISBN
登録日 2020.06.27
更新日 2020.06.28