The expander hierarchy and its applications to dynamic graph algorithms
2021
We introduce a notion for hierarchical graph clustering which we call the expander hierarchy and show a fully dynamic algorithm for maintaining such a hierarchy on a graph with n vertices undergoing edge insertions and deletions using no(1) update time. An expander hierarchy is a tree representation of graphs that faithfully captures the cut-flow structure and consequently our dynamic algorithm almost immediately implies several results including:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI