Copertina

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bodwin, Greg, Hoppenworth, Gary
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Multiplicative Spanners in Minor-Free Graphs
di: Bodwin, Greg, et al.
Pubblicazione: (2025)

New Separations and Reductions for Directed Preservers and Hopsets
di: Hoppenworth, Gary, et al.
Pubblicazione: (2024)

Additive Spanner Lower Bounds with Optimal Inner Graph Structure
di: Bodwin, Greg, et al.
Pubblicazione: (2024)

Greedy Algorithms for Shortcut Sets and Hopsets
di: Bals, Ben, et al.
Pubblicazione: (2025)

The Discrepancy of Shortest Paths
di: Bodwin, Greg, et al.
Pubblicazione: (2024)

An Alternate Proof of Near-Optimal Light Spanners
di: Bodwin, Greg
Pubblicazione: (2023)

Simple Linear-Size Additive Emulators
di: Hoppenworth, Gary
Pubblicazione: (2023)

Near-Optimal Fault-Tolerant Strong Connectivity Preservers
di: Hoppenworth, Gary, et al.
Pubblicazione: (2025)

Improved Online Reachability Preservers
di: Bodwin, Greg, et al.
Pubblicazione: (2024)

A Lower Bound for Light Spanners in General Graphs
di: Bodwin, Greg, et al.
Pubblicazione: (2024)

Improved Shortest Path Restoration Lemmas for Multiple Edge Failures: Trade-offs Between Fault-tolerance and Subpaths
di: Bodwin, Greg, et al.
Pubblicazione: (2023)

Improved Upper Bounds for the Directed Flow-Cut Gap
di: Bodwin, Greg, et al.
Pubblicazione: (2026)

A Unified View of Graph Regularity via Matrix Decompositions
di: Bodwin, Greg, et al.
Pubblicazione: (2019)

Notes on the Linear Algebraic View of Regularity Lemmas
di: Bodwin, Greg, et al.
Pubblicazione: (2025)

Approximation Algorithms for Optimal Hopsets
di: Dinitz, Michael, et al.
Pubblicazione: (2025)

Low Sensitivity Hopsets
di: Ashvinkumar, Vikrant, et al.
Pubblicazione: (2024)

Are there graphs whose shortest path structure requires large edge weights?
di: Bernstein, Aaron, et al.
Pubblicazione: (2023)

Covering Approximate Shortest Paths with DAGs
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

A Unified Framework for Hopsets and Spanners
di: Neiman, Ofer, et al.
Pubblicazione: (2021)

Reducing Shortcut and Hopset Constructions to Shallow Graphs
di: Haeupler, Bernhard, et al.
Pubblicazione: (2025)

Closing the Gap Between Directed Hopsets and Shortcut Sets
di: Bernstein, Aaron, et al.
Pubblicazione: (2022)

Simple Length-Constrained Expander Decompositions
di: Bodwin, Greg, et al.
Pubblicazione: (2025)

Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
di: Bodwin, Greg, et al.
Pubblicazione: (2022)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

Faster $(Δ+ 1)$-Edge Coloring: Breaking the $m \sqrt{n}$ Time Barrier
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2024)

Light Edge Fault Tolerant Graph Spanners
di: Bodwin, Greg, et al.
Pubblicazione: (2025)

On the Hardness Hierarchy for the $O(n \sqrt{\log n})$ Complexity in the Word RAM
di: Kempa, Dominik, et al.
Pubblicazione: (2025)

Revisiting the Folklore Algorithm for Random Access to Grammar-Compressed Strings
di: Cleary, Alan M., et al.
Pubblicazione: (2024)

Submodular Maximization in Exactly $n$ Queries
di: Balkanski, Eric, et al.
Pubblicazione: (2024)

Gabow's $O(\sqrt{n}m)$ Maximum Cardinality Matching Algorithm, Revisited
di: Mehlhorn, Kurt, et al.
Pubblicazione: (2026)

Reviving Thorup's Shortcut Conjecture
di: Bernstein, Aaron, et al.
Pubblicazione: (2025)

A simpler and parallelizable $O(\sqrt{\log n})$-approximation algorithm for Sparsest Cut
di: Kolmogorov, Vladimir
Pubblicazione: (2023)

Exact (n + 2) Comparison Complexity for the N-Repeated Element Problem
di: Au, Andrew
Pubblicazione: (2026)

A Refutation of Elmasry's $\tilde{O}(m \sqrt{n})$-Time Algorithm for Single-Source Shortest Paths
di: Atalig, Sunny, et al.
Pubblicazione: (2025)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
di: Khanna, Sanjeev, et al.
Pubblicazione: (2026)

Faster Multi-Source Reachability and Approximate Distances via Shortcuts, Hopsets and Matrix Multiplication
di: Elkin, Michael, et al.
Pubblicazione: (2025)

Nearly Optimal Dynamic Set Cover: Breaking the Quadratic-in-$f$ Time Barrier
di: Bukov, Anton, et al.
Pubblicazione: (2023)

Optimal Phylogenetic Reconstruction from Sampled Quartets
di: Arvanitakis, Dionysis, et al.
Pubblicazione: (2026)

Exact Sampling of Permutations with a Fixed Longest Increasing Subsequence
di: Clifford, Peter, et al.
Pubblicazione: (2026)

An $O(n^5)$-Time Algorithm for Optimal Broadcast Domination
di: Papadopoulos, Kleitos
Pubblicazione: (2026)