Cover Image

Path-Reporting Distance Oracles with Linear Size

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Neiman, Ofer, Shabat, Idan
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Path-Reporting Distance Oracles with Logarithmic Stretch and Size O(n loglog n)
by: Elkin, Michael, et al.
Published: (2023)

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

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

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

Lightweight Near-Additive Spanners
by: Gitlitz, Yuval, et al.
Published: (2024)

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

Hamming Distance Oracle
by: Boneh, Itai, et al.
Published: (2024)

Distributed Distance Sensitivity Oracles
by: Manoharan, Vignesh, et al.
Published: (2024)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Simple Linear-Size Additive Emulators
by: Hoppenworth, Gary
Published: (2023)

Verifying Shortest Paths in Linear Time
by: Shokry, Ahmed, et al.
Published: (2024)

Deterministic $(2/3-\varepsilon)$-Approximation of Matroid Intersection Using Nearly-Linear Independence-Oracle Queries
by: Terao, Tatsuya
Published: (2024)

Hyper-distance Oracles in Hypergraphs
by: Preti, Giulia, et al.
Published: (2023)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
by: Haeupler, Bernhard, et al.
Published: (2025)

Color Fault-Tolerant Distance Preservers: Õptimal Size in Conditionally Õptimal Time
by: Parter, Merav, et al.
Published: (2025)

Optimal Sensitivity Oracle for Steiner Mincut
by: Bhanja, Koustav
Published: (2024)

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

Combinatorial Optimization using Comparison Oracles
by: Cohen-Addad, Vincent, et al.
Published: (2025)

Near-optimal Size Linear Sketches for Hypergraph Cut Sparsifiers
by: Khanna, Sanjeev, et al.
Published: (2024)

Single-Source Regular Path Querying in Terms of Linear Algebra
by: Belyanin, Georgiy, et al.
Published: (2024)

An Optimal $3$-Fault-Tolerant Connectivity Oracle
by: Kosinas, Evangelos
Published: (2025)