Image de couverture de livre

A Nearly Linear Time Construction of Approximate Single-Source Distance Sensitivity Oracles

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Harada, Kaito, Kitamura, Naoki, Izumi, Taisuke, Masuzawa, Toshimitsu
Format:	Preprint
Publié:	2024
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

Independent Set Reconfiguration Under Bounded-Hop Token
par: Hatano, Hiroki, et autres
Publié: (2024)

A Nearly Linear-Time Distributed Algorithm for Maximum Cardinality Matching
par: Izumi, Taisuke, et autres
Publié: (2023)

Approximate Distance Sensitivity Oracles in Subquadratic Space
par: Bilò, Davide, et autres
Publié: (2023)

Forgetting Alternation and Blossoms: A New Framework for Fast Matching Augmentation and Its Applications to Sequential/Distributed/Streaming Computation
par: Izumi, Taisuke, et autres
Publié: (2025)

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

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

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

Nearly Optimal Fault Tolerant Distance Oracle
par: Dey, Dipan, et autres
Publié: (2024)

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

Path-Reporting Distance Oracles with Linear Size
par: Neiman, Ofer, et autres
Publié: (2024)

Near Optimal Dual Fault Tolerant Distance Oracle
par: Dey, Dipan, et autres
Publié: (2024)

Faster Construction of a Planar Distance Oracle with Õ(1) Query Time
par: Boneh, Itai, et autres
Publié: (2025)

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

Approximating Partition in Near-Linear Time
par: Chen, Lin, et autres
Publié: (2024)

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

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

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

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

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

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

Approximating the Geometric Knapsack Problem in Near-Linear Time and Dynamically
par: Buchem, Moritz, et autres
Publié: (2024)

An Improved Quality Hierarchical Congestion Approximator in Near-Linear Time
par: Henzinger, Monika, et autres
Publié: (2025)

Near Linear Time Approximation Schemes for Clustering of Partially Doubling Metrics
par: Driemel, Anne, et autres
Publié: (2026)

Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time
par: Fischer, Nick, et autres
Publié: (2024)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
par: Bernstein, Aaron, et autres
Publié: (2022)

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)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
par: Fischer, Nick, et autres
Publié: (2024)

Path-Reporting Distance Oracles for Vertex-Labeled Graphs
par: Neiman, Ofer, et autres
Publié: (2026)

Faster Algorithms for $(2k-1)$-Stretch Distance Oracles
par: Kadria, Avi, et autres
Publié: (2025)

Vizing's Theorem in Near-Linear Time
par: Assadi, Sepehr, et autres
Publié: (2024)

Parallel Approximate Maximum Flows in Near-Linear Work and Polylogarithmic Depth
par: Agarwal, Arpit, et autres
Publié: (2024)

Fault-Tolerant Distance Oracles Below the $n \cdot f$ Barrier
par: Khanna, Sanjeev, et autres
Publié: (2026)

Better Decremental and Fully Dynamic Sensitivity Oracles for Subgraph Connectivity
par: Long, Yaowei, et autres
Publié: (2024)

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

$(1-ε)$-Approximation of Knapsack in Nearly Quadratic Time
par: Mao, Xiao
Publié: (2023)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
par: Dai, Jiangqi, et autres
Publié: (2025)

Improved Tree Sparsifiers in Near-Linear Time
par: Agassy, Daniel, et autres
Publié: (2025)

Approximating Directed Connectivity in Almost-Linear Time
par: Quanrud, Kent
Publié: (2025)

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