Copertina

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Mao, Xiao
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Fully Dynamic Set Cover: Worst-Case Recourse and Update Time
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2025)

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs
di: Das, Debarati, et al.
Pubblicazione: (2026)

Fully Dynamic Shortest Paths in Sparse Digraphs
di: Karczmarz, Adam, et al.
Pubblicazione: (2024)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
di: Dory, Michal, et al.
Pubblicazione: (2022)

All-Pairs Shortest Paths with Few Weights per Node
di: Abboud, Amir, et al.
Pubblicazione: (2025)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
di: Meierhans, Simon, et al.
Pubblicazione: (2025)

Adaptive Fully Dynamic $k$-Center Clustering with (Near-)Optimal Worst-Case Guarantees
di: Grilnberger, Mara, et al.
Pubblicazione: (2026)

All-Hops Shortest Paths
di: Williams, Virginia Vassilevska, et al.
Pubblicazione: (2024)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
di: Meierhans, Simon, et al.
Pubblicazione: (2025)

(Worst-Case) Optimal Adaptive Dynamic Bitvectors
di: Navarro, Gonzalo
Pubblicazione: (2024)

A Simple, Nearly-Optimal Algorithm for Differentially Private All-Pairs Shortest Distances
di: Campbell, Jesse, et al.
Pubblicazione: (2024)

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

Fully Dynamic k-Means Coreset in Near-Optimal Update Time
di: la Tour, Max Dupré, et al.
Pubblicazione: (2024)

Fully Dynamic $k$-Median with Near-Optimal Update Time and Recourse
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2024)

Optimal Static Dictionary with Worst-Case Constant Query Time
di: Hu, Yang, et al.
Pubblicazione: (2024)

A fast algorithm for All-Pairs-Shortest-Paths suitable for neural networks
di: Jing, Zeyu, et al.
Pubblicazione: (2023)

All-Pairs Suffix-Prefix on Fully Dynamic Set of Strings
di: Kikuchi, Masaru, et al.
Pubblicazione: (2024)

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

Improved All-Pairs Approximate Shortest Paths in Congested Clique
di: Bui, Hong Duc, et al.
Pubblicazione: (2024)

The Discrepancy of Shortest Paths
di: Bodwin, Greg, et al.
Pubblicazione: (2024)

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

Count-Min Sketch with Conservative Updates: Worst-Case Analysis
di: Mazziane, Younes Ben, et al.
Pubblicazione: (2024)

On Constrained and k Shortest Paths
di: Bendahi, Abderrahim, et al.
Pubblicazione: (2024)

Shortest Paths in Multimode Graphs
di: Kirkpatrick, Yael, et al.
Pubblicazione: (2025)

Fully Dynamic $k$-Clustering with Fast Update Time and Small Recourse
di: Bhattacharya, Sayan, et al.
Pubblicazione: (2024)

Fully Dynamic Euclidean Bi-Chromatic Matching in Sublinear Update Time
di: Goranci, Gramoz, et al.
Pubblicazione: (2025)

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

Negative-Weight Single-Source Shortest Paths in Near-linear Time
di: Bernstein, Aaron, et al.
Pubblicazione: (2022)

The Steiner Shortest Path Tree Problem
di: Asher, Omer, et al.
Pubblicazione: (2025)

Hierarchical Multicriteria Shortest Path Search
di: Kurbanov, Temirlan, et al.
Pubblicazione: (2025)

Covering Approximate Shortest Paths with DAGs
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

Shortcutting for Negative-Weight Shortest Path
di: Li, George Z., et al.
Pubblicazione: (2025)

Breaking the Sorting Barrier for Directed Single-Source Shortest Paths
di: Duan, Ran, et al.
Pubblicazione: (2025)

Parallel Batch-Dynamic Coreness Decomposition with Worst-Case Guarantees
di: Ghaffari, Mohsen, et al.
Pubblicazione: (2025)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
di: Brewer, Bruce W., et al.
Pubblicazione: (2025)

Sensitivity Sampling for $k$-Means: Worst Case and Stability Optimal Coreset Bounds
di: Bansal, Nikhil, et al.
Pubblicazione: (2024)

Hardness of Approximation for Shortest Path with Vector Costs
di: Carlson, Charlie, et al.
Pubblicazione: (2025)

Parameterized Complexity of Finding Dissimilar Shortest Paths
di: Funayama, Ryo, et al.
Pubblicazione: (2024)

On Incremental Approximate Shortest Paths in Directed Graphs
di: Górkiewicz, Adam, et al.
Pubblicazione: (2025)

Breaking the Bellman-Ford Shortest-Path Bound
di: Elmasry, Amr
Pubblicazione: (2024)