Near optimal algorithms for the single source replacement paths problem

DOI10.1137/1.9781611975482.126MaRDI QIDQ5236312zbMATH OpenOpenAlexFDO

Authors Shiri Chechik, Sarel Cohen

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975482.126

Mathematics Subject Classification ID

Paths and cycles (05C38) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Randomized algorithms (68W20)

Recommendations

• A simple algorithm for replacement paths problem
• Improved algorithms for replacement paths problems in restricted graphs
• Automata, Languages and Programming
• Faster replacement paths
• On the difficulty of some shortest path problems

Cited in

(10)

• Distributed constructions of dual-failure fault-tolerant distance preservers
• Near optimal algorithm for the directed single source replacement paths problem
• Near optimal algorithm for fault tolerant distance oracle and single source replacement path problem
• Restorable shortest path tiebreaking for edge-faulty graphs
• Fault tolerant max-cut
• Faster monotone min-plus product, range mode, and single source replacement paths
• A nearly linear time construction of approximate single-source distance sensitivity oracles
• A deterministic approach to shortest path restoration in edge faulty graphs
• Undirected 3-fault replacement path in nearly cubic time
• Incremental distance products via faulty shortest paths

This page was built for publication: Near optimal algorithms for the single source replacement paths problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236312)