Imagen de Portada

Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)

Fuente: arXiv

Guardado en:

Detalles Bibliográficos
Autores principales:	Elkin, Michael, Shabat, Idan
Formato:	Preprint
Publicado:	2023
Materias:	Data Structures and Algorithms
Acceso en línea:	Acceder al recurso
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

Ejemplares similares

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

Spanning and Metric Tree Covers Parameterized by Treewidth
por: Elkin, Michael, et al.
Publicado: (2025)

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

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

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

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

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

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

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

Hamming Distance Oracle
por: Boneh, Itai, et al.
Publicado: (2024)

Distributed Distance Sensitivity Oracles
por: Manoharan, Vignesh, et al.
Publicado: (2024)

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

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

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

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

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
por: Boneh, Itai, et al.
Publicado: (2025)

New Diameter Approximations via Distance Oracle Techniques
por: Kirkpatrick, Yael, et al.
Publicado: (2026)

Near Optimal Dual Fault Tolerant Distance Oracle
por: Dey, Dipan, et al.
Publicado: (2024)

Light Tree Covers, Routing, and Path-Reporting Oracles via Spanning Tree Covers in Doubling Graphs
por: Chang, Hsien-Chih, et al.
Publicado: (2025)

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

Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
por: Manoharan, Vignesh, et al.
Publicado: (2025)

Almost Linear Size Edit Distance Sketch
por: Koucký, Michal, et al.
Publicado: (2024)

Tradeoffs between Mistakes and ERM Oracle Calls in Online and Transductive Online Learning
por: Attias, Idan, et al.
Publicado: (2025)

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

An $O(n\log n)$ Algorithm for Single-Item Lot Sizing with a One-Breakpoint All-Units Discount and Non-Increasing Prices
por: Papadopoulos, Kleitos
Publicado: (2025)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
por: Bernstein, Aaron, et al.
Publicado: (2024)

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

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

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

Time, Message and Memory-Optimal Distributed Minimum Spanning Tree and Partwise Aggregation
por: Goldenfeld, Michael Elkin Tanya
Publicado: (2026)

Deterministic Simple $(Δ+\varepsilonα)$-Edge-Coloring in Near-Linear Time
por: Elkin, Michael, et al.
Publicado: (2024)

Faster Linear-Size And-Or Path and Adder Circuits
por: Brenner, Ulrich, et al.
Publicado: (2024)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
por: Khanna, Sanjeev, et al.
Publicado: (2026)

Matroid Algorithms Under Size-Sensitive Independence Oracles
por: Banihashem, Kiarash, et al.
Publicado: (2026)

Constant-Stretch Rounding on the Hypersimplex
por: Anari, Nima, et al.
Publicado: (2026)

Path Contraction Faster than $2^n$
por: Agrawal, Akanksha, et al.
Publicado: (2025)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
por: Huang, Shang-En, et al.
Publicado: (2016)

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

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
por: Soma, Tasuku, et al.
Publicado: (2025)

$(Δ+ 1)$ Vertex Coloring in $O(n)$ Communication
por: Flin, Maxime, et al.
Publicado: (2024)