Semi-dynamic shortest paths and breadth-first search in digraphs

DOI10.1007/BFB0023446MaRDI QIDQ5047157zbMATH OpenFDO

Authors Roberto Giaccio, Paolo G. Franciosa, Daniele Frigioni

Publication date 9 November 2022

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Data structures (68P05)

Recommendations

• Semi-dynamic breadth-first search in digraphs
• Semidynamic algorithms for maintaining single-source shortest path trees
• Fully Dynamic Algorithms for Maintaining Shortest Paths Trees
• Fully dynamic shortest paths in digraphs with arbitrary arc weights
• Incremental algorithms for minimal length paths

Cites work

• scientific article; zbMATH DE number 3900809 (Why is no real title available?)
• scientific article; zbMATH DE number 3907787 (Why is no real title available?)
• scientific article; zbMATH DE number 1142299 (Why is no real title available?)
• scientific article; zbMATH DE number 871917 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs
• A note on two problems in connexion with graphs
• Amortized Computational Complexity
• An On-Line Edge-Deletion Problem
• Dynamic algorithms for shortest paths in planar graphs
• Faster shortest-path algorithms for planar graphs
• Incremental algorithms for minimal length paths
• Recognizing breadth-first search trees in linear time
• Shortest path queries in digraphs of small treewidth

Cited in

(4)

• Semi-dynamic breadth-first search in digraphs
• A uniform approach to semi-dynamic problems on digraphs
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms
• Finding large \(k\)-clubs in undirected graphs

This page was built for publication: Semi-dynamic shortest paths and breadth-first search in digraphs

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