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

DOI10.1007/BFB0023446zbMATH Open1498.68089MaRDI QIDQ5047157FDOQ5047157

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)

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

Mathematics Subject Classification ID

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

Cites Work

• A note on two problems in connexion with graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• An On-Line Edge-Deletion Problem
• Title not available (Why is that?)
• Faster shortest-path algorithms for planar graphs
• Incremental algorithms for minimal length paths
• Amortized Computational Complexity
• Title not available (Why is that?)
• Dynamic algorithms for shortest paths in planar graphs
• Recognizing breadth-first search trees in linear time
• Title not available (Why is that?)
• Shortest path queries in digraphs of small treewidth
• A fully dynamic approximation scheme for all-pairs shortest paths in planar graphs

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)