Graph Theory, Combinatorics and Algorithms

Cover......Page 1
S Title......Page 2
Title......Page 3
e-ISBN 0-387-25036-0 ......Page 4
Contents ......Page 5
Foreword ......Page 6
The Model ......Page 9
Jacobson\'s Algorithm for adjusting W ......Page 11
The Rate Selection Problem ......Page 13
The Static Case ......Page 16
A Lower Bound ......Page 17
The Dynamic Case ......Page 18
Adversary Restricted to a Fixed Interval ......Page 20
Adversary Restricted by a Multiplicative Factor ......Page 21
Adversary Restricted by an Additive Term ......Page 22
Acknowledgment ......Page 23
References ......Page 24
1. Introduction ......Page 25
2. Optimum Stack Generation Problem ......Page 26
3. Path Compression ......Page 27
4. Amortization and Self-adjusting Search Trees ......Page 32
4.1. Search Trees ......Page 33
4.2. Splay Trees ......Page 35
4.3. Complexity Results ......Page 39
5. The Rotation Distance between Search Trees ......Page 41
6. Static Optimum Search Trees ......Page 42
7. The Minimum Spanning Tree Problem ......Page 43
Acknowledgments ......Page 44
References ......Page 45
1. Introduction ......Page 49
2.1. An Example ......Page 51
2.2. Good News and Bad News ......Page 52
2.3. Interval Graphs and their Applications ......Page 53
3. Coloring Interval Graphs ......Page 54
4. Characterizing Interval Graphs ......Page 56
5. The Berge Mystery Story ......Page 57
Was Desmond Stupid or Just Ignorant? ......Page 58
6. Many Other Families of Intersection Graphs ......Page 59
7. Tolerance Graphs ......Page 62
9. Interval Probe Graphs ......Page 64
11. Conclusion ......Page 67
Further Reading ......Page 68
Additional References ......Page 69
1. Introduction ......Page 71
2. Preliminaries ......Page 78
3. Graph Modules and The r Relation ......Page 79
3.1. Modular Decomposition and Rooted Set Families ......Page 81
3.2. Modular Decomposition and Transitive Orientation ......Page 87
4. Intersection Matrices ......Page 93
4.1. The Delta Modules of an Intersection Matrix ......Page 97
4.2. The Delta Tree and Interval Orientations ......Page 98
5.1. Zero-one Matrices and the Consecutive-ones Property ......Page 102
5.2. Probe Interval Graphs ......Page 108
References ......Page 111
1. Introduction ......Page 114
1.2. Organization ......Page 117
2. Definitions and Notation ......Page 118
3. The Local Ratio Theorem ......Page 119
4. A Framework for Covering Problems ......Page 122
4.1. Partial Set Cover ......Page 124
4.2. A Framework ......Page 126
4.3. Feedback Vertex Set ......Page 128
Minimal solutions and feedback vertex set. ......Page 129
5. Scheduling Problems ......Page 130
5.1. Local Ratio for Maximization Problems ......Page 131
5.2. Throughput Maximization Problems ......Page 132
5.2.1. Interval Scheduling ......Page 133
5.2.4. Scheduling on Parallel Unrelated Machines ......Page 135
5.2.5. Bandwidth Allocation of Sessions in Communication Networks ......Page 136
5.2.7. Throughput Maximization with Batching ......Page 137
5.3. Loss Minimization ......Page 138
5.3.1. Application: General Caching ......Page 140
5.4. Resource Minimization ......Page 141
5.4.1. Bandwidth Trading ......Page 142
5.5. Background ......Page 145
References ......Page 146
1. Introduction ......Page 153
1.1. Why Domination Analysis? ......Page 154
1.2. Introduction to Domination Analysis ......Page 157
1.3. Additional Terminology and Notation ......Page 159
2.1. ATSP Heuristics of Domination Number at Least O((n - 2)!) ......Page 160
2.2. Domination Numbers of Local Search Heuristics ......Page 162
2.3. Upper Bounds for Domination Numbers of ATSP Heuristics ......Page 164
3.1. Minimum Partition and Multiprocessor Scheduling ......Page 166
3.2. Max Cut ......Page 167
3.3. Max-k-SAT ......Page 168
3.4. Fixed Span Frequency Assignment Problem ......Page 170
3.5. DOM-hard Problems ......Page 171
3.6. Other Problems ......Page 172
4. Greedy Algorithm ......Page 173
References ......Page 176
1. Introduction ......Page 181
2. Preliminaries and Definitions ......Page 183
3. Combinatorial Auctions ......Page 185
3.2. Binary Bids ......Page 186
3.2.1. Multi-Unit Binary Combinatorial Auctions ......Page 187
3.3. Beyond Binary Bids ......Page 188
3.4. A Super-Additive Combinatorial Auction ......Page 189
3.5. Combinatorial Network Auctions ......Page 190
4. Constrained Multi-Object Multi-Unit Auction ......Page 191
4.1. Volume Discount ......Page 192
5. Conclusion ......Page 193
References ......Page 194
1. Introduction ......Page 197
2. Lower and Upper Bounds ......Page 199
3. Search on a Tree ......Page 204
4.1. Searching Weakly Cyclic Graphs ......Page 207
4.2. Searching Weakly Eulerian Graphs ......Page 209
5. Simple Graphs Requiring Complicated Search Strategies ......Page 212
6. Search in an Unknown Graph ......Page 215
7.2. Path rules (how to leave a node) ......Page 216
References ......Page 220
1. Introduction ......Page 223
2. Preliminaries ......Page 225
3. Exact Algorithms for the URPP ......Page 226
Frederickson\'s Algorithm ......Page 231
Procedure SHORTEN ......Page 232
Procedure ADD ......Page 233
Procedure CUT ......Page 234
Algorithm DROP-ADD ......Page 236
Variable Neighbourhood Descent ......Page 238
6. Conclusion and Future Developments ......Page 240
References ......Page 241
1. Introduction ......Page 245
2. Covering Suites and Their Properties ......Page 248
3. Orthogonal Arrays and Finite Fields ......Page 249
4. Lower Bounds and Asymptotics ......Page 254
5. Greedy Covering Suites and Probabalistic Constructions ......Page 257
6. Algebraic Constructions ......Page 259
7. Recursive Constructions ......Page 262
8. Heuristics ......Page 266
9.1. Reducing State Machine Models ......Page 268
9.2. Path Coverage Using Covering Suites ......Page 269
9.3. Blind Dyslectic Synchronized Robots on a Line ......Page 270
Acknowledgments ......Page 
References ......Page 272
1. Introduction ......Page 275
Historical perspective and overview. ......Page 277
2. Lower Bounds ......Page 278
Lower bounds for incidences with arbitrary circles. ......Page 280
3. Upper Bounds for Incidences via the Partition Technique ......Page 281
Discussion. ......Page 282
4. Incidences via Crossing Numbers-Szekely\'s Method ......Page 284
Extensions: Many faces and unit circles. ......Page 285
5. Improvements by Cutting into Pseudo-segments ......Page 288
6.1. Points and Lines in Three Dimensions ......Page 291
6.2. Points and Circles in Three and Higher Dimensions ......Page 292
7.1. Algorithmic Issues ......Page 293
7.2. Distinct Distances ......Page 294
7.3. Equal-area, Equal-perimeter, and Isoceles Triangles ......Page 295
7.4. Congruent Simplices ......Page 296
References ......Page 297
Back Cover......Page 301