| Book Name: | Design and Analysis of Algorithms |
| Category: | Algorithms |
| Free Download: | Available |
Design and Analysis of Algorithms
Table of contents :
Preface ……Page 3
Table of Contents ……Page 4
1: Overview of Course ……Page 8
2: Sply Trees ……Page 10
3: Amortized Time for Sply Trees ……Page 13
4: Maintaining Disjoint Sets ……Page 17
5: Binomial heaps ……Page 21
6: F-heap ……Page 25
7: Minimum Spanning Trees ……Page 30
8: Fredman-Tarjan MST Algorithm ……Page 32
9: Branching Problem ……Page 34
10: Light Approximate Shortest Path Trees ……Page 36
11: Matchings ……Page 40
12: Hopcroft-Karp Matching Algorithm ……Page 43
13: Two Processor Scheduling ……Page 46
14: Assignment Problem ……Page 48
15: Network Flow—Maximum Flow Problem ……Page 51
16: The Max Flow Problem ……Page 56
17: An O(n³) Max-Flow Algorithm ……Page 58
18: Vertex Covers and Network Flow ……Page 60
20: Planar Graphs ……Page 65
21: Graph Coloring ……Page 68
22: Graph Minor Theorem and other CS Collectibles ……Page 69
23: The Min Cost Flow Problem ……Page 72
24: Shortest Path based Algorithm for Min Cost Flows ……Page 74
25: NP-completeness……Page 76
26: NP-completeness……Page 78
27: NP-completeness ……Page 80
28: More on NP-completeness ……Page 81
29: 2 Satisfiability ……Page 83
30: Linear Programming ……Page 84
31: Vertex Cover ……Page 89
32: Weighted Vertex Cover ……Page 90
33: A (2 – f(n)) Approximation Algorithm for the Vertex Cover Problem ……Page 94
34: Nemhauser-Trotter Theorem ……Page 97
35: Approximation Algorithms: Set Cover……Page 98
36: Approximation Algorithms: Set Cover and Max Coverage……Page 102
37: Approximation Algorithms: K-Centers ……Page 104
38: Bin Packing ……Page 106
39: Multi-cost Minimum Spanning Trees ……Page 110
40: Set and Vertex Cover Approximations: Randomized Algorithms ……Page 113
41: Steiner Tree Problem ……Page 116
42: Traveling Salesperson and Chinese Postman Problem ……Page 121
43: Vehicle Routing Problems: Stacker Crane……Page 126
45: Unit Capacity Problem (1-delivery TSP) ……Page 129
46: K-capacity Problem ……Page 130
47: Unbounded Capacity Problem ……Page 133
48: Lower Bounds on Approximations ……Page 134
49: Lower Bounds on Approximations (contd) ……Page 139
50: Linear Programming: The Use of Duality ……Page 142
51: Using duality to analyze (and design) approximation algorithms ……Page 147
52: A General Approximation Technique for Constrained Forest Problems ……Page 152
53: On Lİne vs. Off Line: A Measure for Quality Evaluation ……Page 157
References ……Page 160
Design and Analysis of Algorithms
Author(s): Samir Khuller
Year: 2003
