A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems

DOI10.1145/3313276.3316320zbMath1433.68601arXiv1905.11512OpenAlexW2950039944MaRDI QIDQ5212780

Sanjeev Khanna, Julia Chuzhoy

Publication date: 30 January 2020

Published in: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1905.11512

zbMATH Keywords

sparsest cutdecremental single-source shortest pathsvertex-capacitated graphs

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Graph theory (including graph drawing) in computer science (68R10) Approximation algorithms (68W25) Randomized algorithms (68W20) Flows in graphs (05C21)

Related Items (7)

Deterministic Near-Optimal Approximation Algorithms for Dynamic Set Cover ⋮ Single-Source Shortest Paths and Strong Connectivity in Dynamic Planar Graphs. ⋮ A new deterministic algorithm for fully dynamic all-pairs shortest paths ⋮ Deterministic incremental APSP with polylogarithmic update time and stretch ⋮ Temporally connected components ⋮ Single-source shortest paths and strong connectivity in dynamic planar graphs ⋮ Unnamed Item

This page was built for publication: A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems