Cover Image

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Boneh, Itai, Golan, Shay, Mozes, Shay, Prigan, Daniel, Weimann, Oren
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
by: Boneh, Itai, et al.
Published: (2025)

Distances in Planar Graphs are Almost for Free!
by: Mozes, Shay, et al.
Published: (2026)

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

The Complexity of Dynamic LZ77 is $\tildeΘ(n^{2/3})$
by: Boneh, Itai, et al.
Published: (2025)

Deterministic Longest Common Subsequence Approximation in Near-Linear Time
by: Boneh, Itai, et al.
Published: (2025)

Hairpin Completion Distance Lower Bound
by: Boneh, Itai, et al.
Published: (2024)

String 2-Covers with No Length Restrictions
by: Boneh, Itai, et al.
Published: (2024)

Searching 2D-Strings for Matching Frames
by: Boneh, Itai, et al.
Published: (2023)

The Fine-Grained Complexity of Episode Matching
by: Bille, Philip, et al.
Published: (2021)

Bounded Weighted Edit Distance: Dynamic Algorithms and Matching Lower Bounds
by: Boneh, Itai, et al.
Published: (2025)

String Problems in the Congested Clique Model
by: Golan, Shay, et al.
Published: (2025)

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

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

Even Faster $(Δ+ 1)$-Edge Coloring via Shorter Multi-Step Vizing Chains
by: Bhattacharya, Sayan, et al.
Published: (2024)

Approximate Light Spanners in Planar Graphs
by: Le, Hung, et al.
Published: (2025)

A Simple Distributed Deterministic Planar Separator
by: Abd-Elhaleem, Yaseen, et al.
Published: (2026)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

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

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

Distributed Maximum Flow in Planar Graphs
by: Abd-Elhaleem, Yaseen, et al.
Published: (2024)

Balancing Two-Dimensional Straight-Line Programs
by: Boneh, Itai, et al.
Published: (2025)

Dynamic Set Cover with Worst-Case Recourse
by: Solomon, Shay, et al.
Published: (2025)

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

On the Adversarial Robustness of Online Importance Sampling
by: Kenneth-Mordoch, Yotam, et al.
Published: (2025)

Longest Common Extensions with Wildcards: Trade-off and Applications
by: Bathie, Gabriel, et al.
Published: (2024)

Connectivity Labeling in Faulty Colored Graphs
by: Petruschka, Asaf, et al.
Published: (2024)

A Lossless Deamortization for Dynamic Greedy Set Cover
by: Solomon, Shay, et al.
Published: (2024)

Density-Sensitive Algorithms for $(Δ+ 1)$-Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)

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

Towards a Unified Theory of Light Spanners I: Fast (Yet Optimal) Constructions
by: Le, Hung, et al.
Published: (2021)

Vizing's Theorem in Near-Linear Time
by: Assadi, Sepehr, et al.
Published: (2024)

Vizing's Theorem in Deterministic Almost-Linear Time
by: Assadi, Sepehr, et al.
Published: (2025)

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

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

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

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

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

Tree-Like Shortcuttings of Trees
by: Le, Hung, et al.
Published: (2025)

Parks and Recreation: Color Fault-Tolerant Spanners Made Local
by: Parter, Merav, et al.
Published: (2024)

Arboricity-Dependent Algorithms for Edge Coloring
by: Bhattacharya, Sayan, et al.
Published: (2023)