A near-linear-time algorithm for computing replacement paths in planar directed graphs

DOI10.1145/1824777.1824784MaRDI QIDQ2930346zbMATH OpenOpenAlexFDO

Authors Yuval Emek, Liam Roditty, David Peleg

Publication date 18 November 2014

Published in ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1824777.1824784

zbMATH Keywords

planar graphsreplacement paths

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Paths and cycles (05C38) Graph algorithms (graph-theoretic aspects) (05C85) Network design and communication in computer systems (68M10) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05) Programming involving graphs or networks (90C35)

Recommendations

• Solving the replacement paths problem for planar directed graphs in O(n n) time
• A nearly optimal algorithm for approximating replacement paths and k shortest simple paths in general graphs
• Improved algorithms for replacement paths problems in restricted graphs
• Faster replacement paths algorithm for undirected, positive integer weighted graphs with small diameter
• A linear-time algorithm for edge-disjoint paths in planar graphs
• Faster replacement paths algorithms in case of edge or node failure for undirected, positive integer weighted graphs
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• Automata, Languages and Programming
• Replacement paths and k simple shortest paths in unweighted directed graphs
• scientific article; zbMATH DE number 6783474

Cited in

(10)

• Optimal shortest path set problem in undirected graphs
• The online replacement path problem
• Replacement paths and k simple shortest paths in unweighted directed graphs
• Deterministic Combinatorial Replacement Paths and Distance Sensitivity Oracles
• scientific article; zbMATH DE number 6783474 (Why is no real title available?)
• Solving the replacement paths problem for planar directed graphs in O(n n) time
• Fault-tolerant distance labeling for planar graphs
• Fault-tolerant distance labeling for planar graphs
• Distributed constructions of dual-failure fault-tolerant distance preservers
• Simplifying and unifying replacement paths algorithms in weighted directed graphs

This page was built for publication: A near-linear-time algorithm for computing replacement paths in planar directed graphs

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