Semi-dynamic breadth-first search in digraphs

DOI10.1016/S0304-3975(99)00132-2MaRDI QIDQ1589436zbMATH OpenOpenAlexWikidataFDO

Authors Paolo G. Franciosa, Daniele Frigioni, Roberto Giaccio

Publication date 12 December 2000

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0304-3975(99)00132-2

zbMATH Keywords

shortest pathsincremental algorithmsamortized analysisbreadth-first search treedecremental algorithms

Mathematics Subject Classification ID

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

Recommendations

• Semi-dynamic shortest paths and breadth-first search in digraphs
• scientific article; zbMATH DE number 5734730
• scientific article; zbMATH DE number 4049076
• Digraph searching, directed vertex separation and directed pathwidth
• Theory and techniques for synthesizing efficient breadth-first search algorithms
• A breadth-first search with betweenness
• On dynamic breadth-first search in external-memory
• Binary search in graphs revisited
• Binary search in graphs revisited
• Dynamic algorithms for graphs of bounded treewidth

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• 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 1256679 (Why is no real title available?)
• scientific article; zbMATH DE number 1305092 (Why is no real title available?)
• scientific article; zbMATH DE number 1306899 (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?)
• A Separator Theorem for 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 algorithms for the shortest path problem
• Faster shortest-path algorithms for planar graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• Incremental algorithms for minimal length paths
• Maintaining a topological order under edge insertions
• Network flows. Theory, algorithms, and applications.
• On the computational complexity of dynamic graph problems
• Parallel concepts in graph theory
• Recognizing breadth-first search trees in linear time
• Semi-dynamic breadth-first search in digraphs
• Semidynamic algorithms for maintaining single-source shortest path trees
• Shortest path queries in digraphs of small treewidth
• The incremental maintenance of a depth-first-search tree in directed acyclic graphs

Cited in

(10)

• Depth First Search in the Semi-streaming Model
• On dynamic breadth-first search in external-memory
• Semi-dynamic breadth-first search in digraphs
• Lifelong planning \(\text{A}^*\)
• A uniform approach to semi-dynamic problems on digraphs
• Semi-dynamic shortest paths and breadth-first search in digraphs
• On Dynamic DFS Tree in Directed Graphs
• scientific article; zbMATH DE number 5734730 (Why is no real title available?)
• Amortized efficiency of a path retrieval data structure
• On BF-orderable graphs

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

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