Spanning Trees and Optimization Problems

Spanning Trees & Optimization of Problems......Page 2
Preface......Page 6
About the Authors......Page 8
Table of Contents......Page 9
1.1 Counting Spanning Trees......Page 13
2.1 Introduction......Page 21
2.2 Bor°uvka’s Algorithm......Page 23
2.3 Prim’s Algorithm......Page 25
2.4 Kruskal’s Algorithm......Page 27
2.5.4 Clustering gene expression data......Page 29
2.6 Summary......Page 30
Bibliographic Notes and Further Reading......Page 31
Exercises......Page 32
3.1 Introduction......Page 34
3.2 Dijkstra’s Algorithm......Page 36
3.3 The Bellman-Ford Algorithm......Page 44
3.4 Applications......Page 46
3.4.2 SPT-based approximations......Page 48
Bibliographic Notes and Further Reading......Page 49
Exercises......Page 50
4.1 Introduction......Page 52
4.2.1 A simple analysis......Page 55
4.2.2 Solution decomposition......Page 57
4.3.1 Separators and general stars......Page 58
4.3.2 A 15/8-approximation algorithm......Page 63
4.3.3 A 3/2-approximation algorithm......Page 66
4.3.4 Further improvement......Page 68
4.4 A Reduction to the Metric Case......Page 69
4.5.1 Overview......Page 73
4.5.2 The δ-spine of a tree......Page 77
4.5.3 Lower bound......Page 80
4.5.4 From trees to stars......Page 81
4.5.5.1 A polynomial-time method......Page 85
4.5.5.2 A faster method......Page 86
4.6.2 Computational biology......Page 90
4.6.2.1 Multiple sequence alignments......Page 91
4.6.2.3 Tree-driven SP-alignment......Page 92
Bibliographic Notes and Further Reading......Page 93
Exercises......Page 94
5.1 Introduction......Page 96
5.2.1 Overview......Page 98
5.2.2.1 Centroid and p.r.c. routing loads......Page 99
5.2.2.2 Reduction to metric graphs......Page 100
5.2.2.4 Approximating a PROCT......Page 101
5.2.3 Approximating by 2-stars......Page 102
5.2.3.1 Algorithm......Page 103
5.2.3.2 Approximation ratio......Page 106
5.2.4.1 A pseudo-polynomial time algorithm......Page 109
5.2.4.2 A scaling and rounding algorithm......Page 112
5.2.4.3 Approximation ratio......Page 113
5.3 Sum-Requirement......Page 115
5.4 Multiple Sources......Page 120
5.4.1 Computational complexity for fixed......Page 121
5.4.2 A PTAS for the 2-MRCT......Page 126
5.4.2.1 A simple 2-approximation algorithm......Page 127
5.4.2.2 A PTAS......Page 129
5.5 Applications......Page 135
Bibliographic Notes and Further Reading......Page 136
Exercises......Page 138
6.1 Introduction......Page 140
6.2.1 Overview......Page 141
6.2.2 The algorithm......Page 142
6.2.3 The analysis of the algorithm......Page 145
6.3.1 Overview......Page 147
6.3.2 The algorithm......Page 148
6.3.3 The performance analysis......Page 151
6.4 Applications......Page 154
Bibliographic Notes and Further Reading......Page 155
Exercises......Page 156
7.1 Steiner Minimal Trees......Page 158
7.1.1 Approximation by MST......Page 159
7.1.2 Improved approximation algorithms......Page 162
7.2.1 Eccentricities, diameters, and radii......Page 165
7.2.2 The minimum diameter spanning trees......Page 168
7.2.2.1 An algorithm......Page 171
7.2.2.2 The absolute 1-center......Page 172
7.3.1 Leafy trees and leafy forests......Page 173
7.3.2 The algorithm......Page 176
7.3.3 Performance ratio......Page 177
7.4 Some Other Problems......Page 179
7.4.1 Network design......Page 180
7.4.2.1 Reconstructing trees from perfect data......Page 181
7.4.2.2 Reconstructing tree from nonperfect data......Page 183
Bibliographic Notes and Further Reading......Page 184
Exercises......Page 185
References......Page 186