Cover Image

Improved Distance (Sensitivity) Oracles with Subquadratic Space

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Bilò, Davide, Chechik, Shiri, Choudhary, Keerti, Cohen, Sarel, Friedrich, Tobias, Schirneck, Martin
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

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

Simpler and Improved Replacement Path Coverings
by: Bilò, Davide, et al.
Published: (2026)

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

Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
by: Bilò, Davide, et al.
Published: (2024)

Streaming Edge Coloring with Subquadratic Palette Size
by: Chechik, Shiri, et al.
Published: (2023)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
by: Ahi, Mridul, et al.
Published: (2025)

Transversal Rank, Conformality and Enumeration
by: Schirneck, Martin
Published: (2026)

Improved Streaming Edge Coloring
by: Chechik, Shiri, et al.
Published: (2025)

Faster Algorithms for Dual-Failure Replacement Paths
by: Chechik, Shiri, et al.
Published: (2024)

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

Graph Spanners for Group Steiner Distances
by: Bilò, Davide, et al.
Published: (2024)

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
by: Choudhary, Keerti, et al.
Published: (2025)

Computing Flows in Subquadratic Space
by: Brand, Jan van den, et al.
Published: (2026)

Faster Deterministic Streaming Vertex Coloring
by: Chechik, Shiri, et al.
Published: (2026)

Girth Approximations in the CONGEST Model
by: Chechik, Shiri, et al.
Published: (2026)

Fréchet Distance in Subquadratic Time
by: Cheng, Siu-Wing, et al.
Published: (2024)

A New Approach for Approximating Directed Rooted Networks
by: Cohen, Sarel, et al.
Published: (2024)

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

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

Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic Approximation
by: Bläsius, Thomas, et al.
Published: (2024)

Fault-Tolerant Bounded Flow Preservers
by: Bansal, Shivam, et al.
Published: (2024)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
by: Mao, Xiao, et al.
Published: (2026)

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

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

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

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
by: Bille, Philip, et al.
Published: (2022)

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

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
by: Cheng, Siu-Wing, et al.
Published: (2025)

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

Weakly Approximating Knapsack in Subquadratic Time
by: Chen, Lin, et al.
Published: (2025)

A Subquadratic Bound for Online Bisection
by: Bienkowski, Marcin, et al.
Published: (2023)

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

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

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

Approximately Counting Knapsack Solutions in Subquadratic Time
by: Feng, Weiming, et al.
Published: (2024)

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)

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

Temporal queries for dynamic temporal forests
by: Bilò, Davide, et al.
Published: (2024)

Subquadratic Submodular Maximization with a General Matroid Constraint
by: Kobayashi, Yusuke, et al.
Published: (2024)