Buchumschlag

A Near-Optimal Offline Algorithm for Dynamic All-Pairs Shortest Paths in Planar Digraphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Das, Debarati, Gutenberg, Maximilian Probst, Wulff-Nilsen, Christian
Format:	Preprint
Veröffentlicht:	2026
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Parallel Reachability and Shortest Paths on Non-sparse Digraphs: Near-linear Work and Sub-square-root Depth
von: Ashvinkumar, Vikrant, et al.
Veröffentlicht: (2026)

Near-Optimal Algorithm for Directed Expander Decompositions
von: Sulser, Aurelio L., et al.
Veröffentlicht: (2024)

Negative-Weight Single-Source Shortest Paths in Near-linear Time
von: Bernstein, Aaron, et al.
Veröffentlicht: (2022)

Parallel and Distributed Expander Decomposition: Simple, Fast, and Near-Optimal
von: Chen, Daoyuan, et al.
Veröffentlicht: (2024)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
von: Meierhans, Simon, et al.
Veröffentlicht: (2025)

Fully Dynamic Shortest Paths in Sparse Digraphs
von: Karczmarz, Adam, et al.
Veröffentlicht: (2024)

A Simple, Nearly-Optimal Algorithm for Differentially Private All-Pairs Shortest Distances
von: Campbell, Jesse, et al.
Veröffentlicht: (2024)

A Simple Deterministic Reduction From Gomory-Hu Tree to Maxflow and Expander Decomposition
von: Gutenberg, Maximilian Probst, et al.
Veröffentlicht: (2025)

Optimal Electrical Oblivious Routing on Expanders
von: Florescu, Cella, et al.
Veröffentlicht: (2024)

Fully-Dynamic All-Pairs Shortest Paths: Likely Optimal Worst-Case Update Time
von: Mao, Xiao
Veröffentlicht: (2023)

An Approximation Algorithm for Graph Label Selection
von: John, Josia, et al.
Veröffentlicht: (2026)

Expander Pruning with Polylogarithmic Worst-Case Recourse and Update Time
von: Meierhans, Simon, et al.
Veröffentlicht: (2025)

Random-Shift Revisited: Tight Approximations for Tree Embeddings and L1-Oblivious Routings
von: Kyng, Rasmus, et al.
Veröffentlicht: (2025)

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths
von: Dory, Michal, et al.
Veröffentlicht: (2022)

All-Pairs Shortest Paths with Few Weights per Node
von: Abboud, Amir, et al.
Veröffentlicht: (2025)

A Simple and Fast Reduction from Gomory-Hu Trees to Polylog Maxflows
von: Gutenberg, Maximilian Probst, et al.
Veröffentlicht: (2025)

All-Hops Shortest Paths
von: Williams, Virginia Vassilevska, et al.
Veröffentlicht: (2024)

Planar Disjoint Shortest Paths is Fixed-Parameter Tractable
von: Pilipczuk, Michał, et al.
Veröffentlicht: (2025)

Fully Dynamic Strongly Connected Components in Planar Digraphs
von: Karczmarz, Adam, et al.
Veröffentlicht: (2024)

Node-Weighted Multicut in Planar Digraphs
von: Chekuri, Chandra, et al.
Veröffentlicht: (2026)

A fast algorithm for All-Pairs-Shortest-Paths suitable for neural networks
von: Jing, Zeyu, et al.
Veröffentlicht: (2023)

A Simple Parallel Algorithm with Near-Linear Work for Negative-Weight Single-Source Shortest Paths
von: Fischer, Nick, et al.
Veröffentlicht: (2024)

An Optimal Algorithm for Shortest Paths in Unweighted Disk Graphs
von: Brewer, Bruce W., et al.
Veröffentlicht: (2025)

Almost-Linear Time Algorithms for Decremental Graphs: Min-Cost Flow and More via Duality
von: Brand, Jan van den, et al.
Veröffentlicht: (2024)

Deterministic Negative-Weight Shortest Paths in Nearly Linear Time via Path Covers
von: Haeupler, Bernhard, et al.
Veröffentlicht: (2025)

A Polylogarithmic Approximation for Directed Steiner Forest in Planar Digraphs
von: Chekuri, Chandra, et al.
Veröffentlicht: (2024)

Fully Dynamic Exact Edge Connectivity in Sublinear Time
von: Goranci, Gramoz, et al.
Veröffentlicht: (2023)

Improved All-Pairs Approximate Shortest Paths in Congested Clique
von: Bui, Hong Duc, et al.
Veröffentlicht: (2024)

Faster Approximation Algorithms for Restricted Shortest Paths in Directed Graphs
von: Ashvinkumar, Vikrant, et al.
Veröffentlicht: (2024)

Efficient Algorithms for Disjoint Shortest Paths Problem and its Extensions
von: Choudhary, Keerti, et al.
Veröffentlicht: (2025)

The Discrepancy of Shortest Paths
von: Bodwin, Greg, et al.
Veröffentlicht: (2024)

On Constrained and k Shortest Paths
von: Bendahi, Abderrahim, et al.
Veröffentlicht: (2024)

Shortest Paths in Multimode Graphs
von: Kirkpatrick, Yael, et al.
Veröffentlicht: (2025)

Approximation Algorithms for Digraph Width Parameters
von: Kintali, Shiva, et al.
Veröffentlicht: (2011)

Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
von: Atalig, Sunny, et al.
Veröffentlicht: (2024)

Deterministic Almost-Linear-Time Gomory-Hu Trees
von: Abboud, Amir, et al.
Veröffentlicht: (2025)

The Steiner Shortest Path Tree Problem
von: Asher, Omer, et al.
Veröffentlicht: (2025)

Verifying Shortest Paths in Linear Time
von: Shokry, Ahmed, et al.
Veröffentlicht: (2024)

Hierarchical Multicriteria Shortest Path Search
von: Kurbanov, Temirlan, et al.
Veröffentlicht: (2025)

Covering Approximate Shortest Paths with DAGs
von: Assadi, Sepehr, et al.
Veröffentlicht: (2025)