Geometric Spanner Networks

ISBN: 9780511267314 出版年：2007 页码：518 Giri Narasimhan Michiel Smid Cambridge University Press

Part I. Introduction: 1. Introduction 2. Algorithms and graphs 3. The algebraic computation-tree model Part II. Spanners Based on Simplical Cones: 4. Spanners based on the Q-graph 5. Cones in higher dimensional space and Q-graphs 6. Geometric analysis: the gap property 7. The gap-greedy algorithm 8. Enumerating distances using spanners of bounded degree Part III. The Well Separated Pair Decomposition and its Applications: 9. The well-separated pair decomposition 10. Applications of well-separated pairs 11. The Dumbbell theorem 12. Shortcutting trees and spanners with low spanner diameter 13. Approximating the stretch factor of Euclidean graphs Part IV. The Path Greedy Algorithm: 14. Geometric analysis: the leapfrog property 15. The path-greedy algorithm Part V. Further Results and Applications: 16. The distance range hierarchy 17. Approximating shortest paths in spanners 18. Fault-tolerant spanners 19. Designing approximation algorithms with spanners 20. Further results and open problems.