Handbook of Data Structures and Applications, 2nd Edition

37

Dynamic Graphs*

Camil Demetrescu

Sapienza University of Rome

Irene Finocchi

Sapienza University of Rome

Giuseppe F. Italiano

University of Rome Tor Vergata

37.1Introduction

37.2Techniques for Undirected Graphs

Clustering•Sparsification•Randomization

37.3Techniques for Directed Graphs

Kleene Closures•Long Paths•Locality•Matrices

37.4Connectivity

Updates in O(log2 n) Time

37.5Minimum Spanning Tree

Deletions in O(log2 n) Time•Updates in O(log4 n) Time

37.6Transitive Closure

Updates in O(n2 log n) Time•Updates in O(n2) Time

37.7All-Pairs Shortest Paths

Updates in O(n2.5Clogn) Time•Updates in O(n2 log3 n) Time

37.8Conclusions

Acknowledgments

References

37.1Introduction

In many applications of graph algorithms, including communication networks, ...