Copertina

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Dory, Michal, Forster, Sebastian, Nazari, Yasamin, de Vos, Tijn
Natura:	Preprint
Pubblicazione:	2022
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Massively Parallel Algorithms for Approximate Shortest Paths
di: Dory, Michal, et al.
Pubblicazione: (2024)

Towards Constant Time Multi-Call Rumor Spreading on Small-Set Expanders
di: Cruciani, Emilio, et al.
Pubblicazione: (2025)

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

Dynamic Matroids: Base Packing and Covering
di: de Vos, Tijn, et al.
Pubblicazione: (2025)

Distributed Sparsest Cut via Eigenvalue Estimation
di: Maus, Yannic, et al.
Pubblicazione: (2025)

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

Approximation Algorithms for Optimal Hopsets
di: Dinitz, Michael, et al.
Pubblicazione: (2025)

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

Tree-Packing Revisited: Faster Fully Dynamic Min-Cut and Arboricity
di: de Vos, Tijn, et al.
Pubblicazione: (2024)

Deterministic Edge Coloring with few Colors in CONGEST
di: Blikstad, Joakim, et al.
Pubblicazione: (2026)

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
di: Mao, Xiao
Pubblicazione: (2023)

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

Dynamic algorithms for k-center on graphs
di: Cruciani, Emilio, et al.
Pubblicazione: (2023)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
di: Pilipczuk, Michał, et al.
Pubblicazione: (2025)

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

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

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

Greedy Algorithms for Shortcut Sets and Hopsets
di: Bals, Ben, et al.
Pubblicazione: (2025)

Improved 2-Approximate Shortest Paths for close vertex pairs
di: Gupta, Manoj
Pubblicazione: (2025)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
di: Ashvinkumar, Vikrant, et al.
Pubblicazione: (2024)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
di: Bentert, Matthias, et al.
Pubblicazione: (2024)

Lower Bounds for Approximate (& Exact) k-Disjoint-Shortest-Paths
di: Chitnis, Rajesh, et al.
Pubblicazione: (2024)

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

Decremental $(1+ε)$-Approximate Maximum Eigenvector: Dynamic Power Method
di: Adil, Deeksha, et al.
Pubblicazione: (2024)

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

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

Parallel Minimum Cost Flow in Near-Linear Work and Square Root Depth for Dense Instances
di: Brand, Jan van den, et al.
Pubblicazione: (2025)

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)

Approximation Algorithms for $\ell_p$-Shortest Path and $\ell_p$-Group Steiner Tree
di: Makarychev, Yury, et al.
Pubblicazione: (2024)

Incremental Approximate Single-Source Shortest Paths with Predictions
di: McCauley, Samuel, et al.
Pubblicazione: (2025)

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

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

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

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

Universally Optimal Decremental Tree Minima
di: Berendsohn, Benjamin Aram
Pubblicazione: (2026)

Constant Approximating Disjoint Paths on Acyclic Digraphs is W[1]-hard
di: Włodarczyk, Michał
Pubblicazione: (2024)

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

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