Copertina

New Diameter Approximations via Distance Oracle Techniques

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Kirkpatrick, Yael, Roditty, Liam, Qi, Richard, Williams, Virginia Vassilevska
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Shortest Paths in Multimode Graphs
di: Kirkpatrick, Yael, et al.
Pubblicazione: (2025)

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
di: Kopelowitz, Tsvi, et al.
Pubblicazione: (2023)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
di: Kadria, Avi, et al.
Pubblicazione: (2025)

Improved Additive Approximation Algorithms for APSP
di: Jin, Ce, et al.
Pubblicazione: (2025)

Improved girth approximation in weighted undirected graphs
di: Kadria, Avi, et al.
Pubblicazione: (2025)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
di: Kirkpatrick, Yael, et al.
Pubblicazione: (2026)

Beyond 2-approximation for k-Center in Graphs
di: Jin, Ce, et al.
Pubblicazione: (2025)

Additive, Near-Additive, and Multiplicative Approximations for APSP in Weighted Undirected Graphs: Trade-offs and Algorithms
di: Roditty, Liam, et al.
Pubblicazione: (2025)

New approximate distance oracles and their applications
di: Kadria, Avi, et al.
Pubblicazione: (2025)

New algorithms for girth and cycle detection
di: Roditty, Liam, et al.
Pubblicazione: (2025)

Fast Approximate Counting of Cycles
di: Censor-Hillel, Keren, et al.
Pubblicazione: (2024)

Undirected Replacement Paths: Dual Fault Reduces to Single Source
di: Nogler, Jakob, et al.
Pubblicazione: (2026)

Listing 6-Cycles in Sparse Graphs
di: Williams, Virginia Vassilevska, et al.
Pubblicazione: (2024)

Faster Algorithms for Text-to-Pattern Hamming Distances
di: Chan, Timothy M., et al.
Pubblicazione: (2023)

Output-sensitive approximate counting via a measure-bounded hyperedge oracle, or: How asymmetry helps estimate $k$-clique counts faster
di: Censor-Hillel, Keren, et al.
Pubblicazione: (2025)

Faster Weighted and Unweighted Tree Edit Distance and APSP Equivalence
di: Nogler, Jakob, et al.
Pubblicazione: (2024)

Approximate Distance Sensitivity Oracles in Subquadratic Space
di: Bilò, Davide, et al.
Pubblicazione: (2023)

Fault-Tolerant ST-Diameter Oracles
di: Bilò, Davide, et al.
Pubblicazione: (2023)

Weighted Emulators with Local Heaviest Edges Stretch for Undirected Graphs
di: Roditty, Liam, et al.
Pubblicazione: (2026)

A Refined Laser Method and Faster Matrix Multiplication
di: Alman, Josh, et al.
Pubblicazione: (2020)

Towards Optimal Output-Sensitive Clique Listing or: Listing Cliques from Smaller Cliques
di: Dalirrooyfard, Mina, et al.
Pubblicazione: (2023)

All-Hops Shortest Paths
di: Williams, Virginia Vassilevska, et al.
Pubblicazione: (2024)

Fault-Tolerant Approximate Distance Oracles with a Source Set
di: Dey, Dipan, et al.
Pubblicazione: (2025)

Detecting Disjoint Shortest Paths in Linear Time and More
di: Akmal, Shyan, et al.
Pubblicazione: (2024)

A Note on the Conditional Optimality of Chiba and Nishizeki's Algorithms
di: Kirkpatrick, Yael, et al.
Pubblicazione: (2024)

Color Distance Oracles and Snippets: Separation Between Exact and Approximate Solutions
di: Horowicz, Noam, et al.
Pubblicazione: (2025)

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

All-Pairs Shortest Paths with Few Weights per Node
di: Abboud, Amir, et al.
Pubblicazione: (2025)

Hamming Distance Oracle
di: Boneh, Itai, et al.
Pubblicazione: (2024)

Lossless Derandomization for Undirected Single-Source Shortest Paths and Approximate Distance Oracles
di: Yan, Shuyi
Pubblicazione: (2025)

A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles
di: Harada, Kaito, et al.
Pubblicazione: (2024)

Distributed Distance Sensitivity Oracles
di: Manoharan, Vignesh, et al.
Pubblicazione: (2024)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
di: Haeupler, Bernhard, et al.
Pubblicazione: (2024)

Going Beyond Surfaces in Diameter Approximation
di: Włodarczyk, Michał
Pubblicazione: (2025)

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter
di: Chalermsook, Parinya, et al.
Pubblicazione: (2021)

Improved Algorithms for Clustering with Noisy Distance Oracles
di: Pradhan, Pinki, et al.
Pubblicazione: (2026)

Improved Distance (Sensitivity) Oracles with Subquadratic Space
di: Bilò, Davide, et al.
Pubblicazione: (2024)

Path-Reporting Distance Oracles with Linear Size
di: Neiman, Ofer, et al.
Pubblicazione: (2024)

Nearly Optimal Fault Tolerant Distance Oracle
di: Dey, Dipan, et al.
Pubblicazione: (2024)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
di: Neiman, Ofer, et al.
Pubblicazione: (2026)