Handbook of Data Structures and Applications, 2nd Edition

39

Randomized Graph Data-Structures for Approximate Shortest Paths^*

Surender Baswana

Indian Institute of Technology, Kanpur

Sandeep Sen

Indian Institute of Technology, Delhi

39.1Introduction

39.2A Randomized Data-Structure for Static APASP: Approximate Distance Oracles

3-Approximate Distance Oracle•Preliminaries•(2k - 1)-Approximate Distance Oracle•Computing Approximate Distance Oracles

39.3A Randomized Data-Structure for Decremental APASP

Main Idea•Notations•Hierarchical Distance Maintaining Data-Structure•Bounding the Size of Bud,S under Edge-Deletions•Improved Decremental Algorithm for APASP up to Distance d

39.4Further Reading and Bibliography

Acknowledgments

References

39.1Introduction

Let G = (V, E) be an undirected weighted graph on ...