Shortest path algorithms for nearly acyclic directed graphs

DOI10.1016/S0304-3975(97)00292-2MaRDI QIDQ1274325zbMATH OpenFDO

Authors Tadao Takaoka

Publication date 12 January 1999

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

Full work available at URL https://doi.org/10.1016/S0304-3975(97)00292-2

zbMATH Keywords

acyclic graphalgorithmDijkstra's algorithmFibonacci heapnearly acyclic graphpriority queueshortest paths

Mathematics Subject Classification ID

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

Recommendations

• Improved shortest path algorithms for nearly acyclic graphs
• scientific article; zbMATH DE number 1576683
• Shortest paths in almost acyclic graphs

Cites work

• A note on two problems in connexion with graphs
• An All Pairs Shortest Path Algorithm with Expected Time $O(n^2 \log n)$
• Depth-First Search and Linear Graph Algorithms
• Fast Algorithms for Shortest Paths in Planar Graphs, with Applications
• Fibonacci heaps and their uses in improved network optimization algorithms
• scientific article; zbMATH DE number 65738 (Why is no real title available?)
• scientific article; zbMATH DE number 1555963 (Why is no real title available?)
• Shortest paths in digraphs of small treewidth. I: Sequential algorithms

Cited in

(14)

• Improved shortest path algorithms for nearly acyclic graphs
• A bidirectional shortest-path algorithm with good average-case behavior
• Approximately counting approximately-shortest paths in directed acyclic graphs
• scientific article; zbMATH DE number 1576683 (Why is no real title available?)
• Shortest paths in nearly conservative digraphs
• Sharing information for the all pairs shortest path problem
• An efficient algorithm to determine all shortest paths in Sierpiński graphs
• Optimally fast shortest path algorithms for some classes of graphs
• scientific article; zbMATH DE number 1798166 (Why is no real title available?)
• The next‐to‐shortest path problem on directed graphs with positive edge weights
• Shortest paths in almost acyclic graphs
• Shortest path algorithms for nearly acyclic directed graphs
• Fixed node determination and analysis in directed acyclic graphs of structured networks
• Solving shortest paths efficiently on nearly acyclic directed graphs

Describes a project that uses

Uses Software

• Algorithm 97

This page was built for publication: Shortest path algorithms for nearly acyclic directed graphs

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