Approximate Spanning Tree Counting from Uncorrelated Edge Sets
We show an $\widetilde{O}(m^{1.5} ε^{-1})$ time algorithm that on a graph with $m$ edges and $n$ vertices outputs its spanning tree count up to a multiplicative $(1+ε)$ factor with high probability, improving on the previous best runtime of $\widetilde{O}(m + n^{1.875}ε^{-7/4})$ in sparse graphs. Wh...
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Artículo |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | https://arxiv.org/abs/2505.14666 http://arxiv.org/abs/2505.14666 |
| Etiquetas: |
Sin Etiquetas, Sea el primero en etiquetar este registro!
|