Fully Dynamic Random-Walk Quantities on Undirected Expanders and $κ$-Uniform Directed Graphs
We study fully dynamic data structures for random-walk quantities on undirected expanders and fast-mixing directed graphs. For an unweighted graph whose normalized Laplacian has spectral gap at least $γ$, we give a $(1\pm\varepsilon)$ effective-resistance data structure with expected update time $O(...
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Artículo |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2610.17712 http://arxiv.org/abs/2610.17712 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|