Cover Image

Solving the all pairs shortest path problem after minor update of a large dense graph

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Liu, Gangli
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

An efficient implementation for solving the all pairs minimax path problem in an undirected dense graph
by: Liu, Gangli
Published: (2024)

Are there graphs whose shortest path structure requires large edge weights?
by: Bernstein, Aaron, et al.
Published: (2023)

Approximating the shortest path problem with scenarios
by: Kasperski, Adam, et al.
Published: (2018)

Recoverable robust shortest path problem under interval budgeted uncertainty representations
by: Jackiewicz, Marcel, et al.
Published: (2024)

Faster negative length shortest paths by bootstrapping hop reducers
by: Huang, Yufan, et al.
Published: (2025)

On graphs coverable by k shortest paths
by: Dumas, Maël, et al.
Published: (2022)

Computational complexity of the recoverable robust shortest path problem in acyclic digraphs
by: Kasperski, Adam, et al.
Published: (2024)

Forcing a unique minimum spanning tree and a unique shortest path
by: Gima, Tatsuya, et al.
Published: (2025)

Faster single-source shortest paths with negative real weights via proper hop distance
by: Huang, Yufan, et al.
Published: (2024)

Graph neural networks extrapolate out-of-distribution for shortest paths
by: Nerem, Robert R., et al.
Published: (2025)

Centrality of shortest paths: Algorithms and complexity results
by: Phosavanh, Johnson, et al.
Published: (2024)

A parallel algorithm for the odd two-face shortest k-disjoint path problem
by: Chakraborty, Srijan, et al.
Published: (2025)

Finding longer cycles via shortest colourful cycle
by: Björklund, Andreas, et al.
Published: (2024)

Faithful universal graphs for minor-closed classes
by: Bastide, Paul, et al.
Published: (2025)

On the closest pair of points problem
by: Hitz, Martin, et al.
Published: (2026)

The trace reconstruction problem for spider graphs
by: Sun, Alec, et al.
Published: (2022)

Faster shortest-path algorithms using the acyclic-connected tree
by: Stefansson, Elis, et al.
Published: (2025)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
by: Kluk, Kacper, et al.
Published: (2025)

Approximating optimization problems in graphs with locational uncertainty
by: Bougeret, Marin, et al.
Published: (2022)

A polynomial delay algorithm generating all potential maximal cliques in triconnected planar graphs
by: Grigoriev, Alexander, et al.
Published: (2025)

Faster algorithms for packing forests in graphs and related problems
by: Arkhipov, Pavel, et al.
Published: (2024)

Fast approximation algorithms for the 1-median problem on real-world large graphs
by: Ueta, Keisuke, et al.
Published: (2025)

Erdős-Gyárfás conjecture on graphs without long induced paths
by: Hegde, Anand Shripad, et al.
Published: (2024)

To buy or not to buy: deterministic rent-or-buy problems on node-weighted graphs
by: Borst, Sander, et al.
Published: (2025)

Solving the unit-load pre-marshalling problem in block stacking storage systems with multiple access directions
by: Pfrommer, Jakob, et al.
Published: (2022)

The problem of computing a $2$-T-connected spanning subgraph with minimum number of edges in directed graphs
by: Jaberi, Raed, et al.
Published: (2024)

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
by: Bonnet, Édouard, et al.
Published: (2026)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
by: Lokshtanov, Daniel, et al.
Published: (2026)

Efficient top-down updates in AVL trees
by: Jugé, Vincent
Published: (2024)

Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
by: An, Shinwoo, et al.
Published: (2024)

Subexponential algorithms in geometric graphs via the subquadratic grid minor property: the role of local radius
by: Berthe, Gaétan, et al.
Published: (2023)

Compressed Game Solving
by: Considine, Jeffrey
Published: (2024)

Subquadratic algorithms in minor-free digraphs: (weighted) distance oracles, decremental reachability, and more
by: Karczmarz, Adam, et al.
Published: (2024)

The complexity of testing all properties of planar graphs, and the role of isomorphism
by: Basu, Sabyasachi, et al.
Published: (2021)

Entrywise Approximate Laplacian Solving
by: Chen, Jingbang, et al.
Published: (2024)

On 2-strong connectivity orientations of mixed graphs and related problems
by: Georgiadis, Loukas, et al.
Published: (2023)

Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than $3^k$
by: Liu, Yuxi, et al.
Published: (2024)

On Solving Linear Systems in Sublinear Time
by: Andoni, Alexandr, et al.
Published: (2018)

Solving Linear Programs with Differential Privacy
by: Ene, Alina, et al.
Published: (2025)

Computing diverse pair of solutions for tractable SAT
by: Gima, Tatsuya, et al.
Published: (2024)