Image de couverture de livre

Approximate Distance Sensitivity Oracles in Subquadratic Space

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Bilò, Davide, Chechik, Shiri, Choudhary, Keerti, Cohen, Sarel, Friedrich, Tobias, Krogmann, Simon, Schirneck, Martin
Format:	Preprint
Publié:	2023
Sujets:	Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Improved Distance (Sensitivity) Oracles with Subquadratic Space
par: Bilò, Davide, et autres
Publié: (2024)

Fault-Tolerant ST-Diameter Oracles
par: Bilò, Davide, et autres
Publié: (2023)

Simpler and Improved Replacement Path Coverings
par: Bilò, Davide, et autres
Publié: (2026)

Efficient Fault-Tolerant Search by Fast Indexing of Subnetworks
par: Bilò, Davide, et autres
Publié: (2024)

Streaming Edge Coloring with Subquadratic Palette Size
par: Chechik, Shiri, et autres
Publié: (2023)

Maximum-Flow and Minimum-Cut Sensitivity Oracles for Directed Graphs
par: Ahi, Mridul, et autres
Publié: (2025)

Girth Approximations in the CONGEST Model
par: Chechik, Shiri, et autres
Publié: (2026)

Transversal Rank, Conformality and Enumeration
par: Schirneck, Martin
Publié: (2026)

A New Approach for Approximating Directed Rooted Networks
par: Cohen, Sarel, et autres
Publié: (2024)

Faster Algorithms for Dual-Failure Replacement Paths
par: Chechik, Shiri, et autres
Publié: (2024)

Robust Parameter Fitting to Realistic Network Models via Iterative Stochastic Approximation
par: Bläsius, Thomas, et autres
Publié: (2024)

Approximation Schemes for Edit Distance and LCS in Quasi-Strongly Subquadratic Time
par: Mao, Xiao, et autres
Publié: (2026)

Distributed Distance Sensitivity Oracles
par: Manoharan, Vignesh, et autres
Publié: (2024)

On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch
par: Kopelowitz, Tsvi, et autres
Publié: (2023)

Graph Spanners for Group Steiner Distances
par: Bilò, Davide, et autres
Publié: (2024)

Constant Approximation of Fréchet Distance in Strongly Subquadratic Time
par: Cheng, Siu-Wing, et autres
Publié: (2025)

A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles
par: Harada, Kaito, et autres
Publié: (2024)

Weakly Approximating Knapsack in Subquadratic Time
par: Chen, Lin, et autres
Publié: (2025)

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
par: Choudhary, Keerti, et autres
Publié: (2025)

Computing Flows in Subquadratic Space
par: Brand, Jan van den, et autres
Publié: (2026)

Faster Deterministic Streaming Vertex Coloring
par: Chechik, Shiri, et autres
Publié: (2026)

Improved Streaming Edge Coloring
par: Chechik, Shiri, et autres
Publié: (2025)

Approximately Counting Knapsack Solutions in Subquadratic Time
par: Feng, Weiming, et autres
Publié: (2024)

Õptimal Fault-Tolerant Labeling for Reachability and Approximate Distances in Directed Planar Graphs
par: Boneh, Itai, et autres
Publié: (2025)

New Diameter Approximations via Distance Oracle Techniques
par: Kirkpatrick, Yael, et autres
Publié: (2026)

Fréchet Distance in Subquadratic Time
par: Cheng, Siu-Wing, et autres
Publié: (2024)

Algorithms for Distance Sensitivity Oracles and other Graph Problems on the PRAM
par: Manoharan, Vignesh, et autres
Publié: (2025)

Fault-Tolerant Approximate Distance Oracles with a Source Set
par: Dey, Dipan, et autres
Publié: (2025)

Fault-Tolerant Bounded Flow Preservers
par: Bansal, Shivam, et autres
Publié: (2024)

A $(1+ε)$-Approximation for Ultrametric Embedding in Subquadratic Time
par: Bathie, Gabriel, et autres
Publié: (2025)

Color Distance Oracles and Snippets: Separation Between Exact and Approximate Solutions
par: Horowicz, Noam, et autres
Publié: (2025)

On the (In)Approximability of the Monitoring Edge Geodetic Set Problem
par: Bilò, Davide, et autres
Publié: (2025)

Preprocessed 3SUM for Unknown Universes with Subquadratic Space
par: Kirkpatrick, Yael, et autres
Publié: (2026)

Hamming Distance Oracle
par: Boneh, Itai, et autres
Publié: (2024)

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

Gapped String Indexing in Subquadratic Space and Sublinear Query Time
par: Bille, Philip, et autres
Publié: (2022)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
par: Haeupler, Bernhard, et autres
Publié: (2024)

A Subquadratic Bound for Online Bisection
par: Bienkowski, Marcin, et autres
Publié: (2023)

Optimal Sensitivity Oracle for Steiner Mincut
par: Bhanja, Koustav
Publié: (2024)

Improved Algorithms for Clustering with Noisy Distance Oracles
par: Pradhan, Pinki, et autres
Publié: (2026)