Solving shortest paths efficiently on nearly acyclic directed graphs

DOI10.1016/J.TCS.2006.10.008MaRDI QIDQ868945zbMATH OpenOpenAlexFDO

Authors S. Saunders, Tadao Takaoka

Publication date 26 February 2007

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

Full work available at URL http://hdl.handle.net/10092/14775

zbMATH Keywords

graph decompositionnearly acyclic graphshortest path algorithm

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Analysis of algorithms (68W40)

Recommendations

• Shortest path algorithms for nearly acyclic directed graphs
• Improved shortest path algorithms for nearly acyclic graphs
• scientific article; zbMATH DE number 1576683
• Shortest paths in almost acyclic graphs
• Approximating Shortest Paths in Graphs
• Computing almost shortest paths
• Computing almost shortest paths (extended abstract)
• Optimally fast shortest path algorithms for some classes of graphs
• Computing the nxm shortest path efficiently
• Counting approximately-shortest paths in directed acyclic graphs

Cites work

• scientific article; zbMATH DE number 1576683 (Why is no real title available?)
• scientific article; zbMATH DE number 1696652 (Why is no real title available?)
• scientific article; zbMATH DE number 3906496 (Why is no real title available?)
• scientific article; zbMATH DE number 1555963 (Why is no real title available?)
• A new approach to all-pairs shortest paths on real-weighted graphs
• A note on two problems in connexion with graphs
• Depth-First Search and Linear Graph Algorithms
• Fibonacci heaps and their uses in improved network optimization algorithms
• Improved shortest path algorithms for nearly acyclic graphs
• Shortest path algorithms for nearly acyclic directed graphs

Cited in

(12)

• Sharing information for the all pairs shortest path problem
• Computing Directed Pathwidth in O(1.89 n ) Time
• Approximately counting approximately-shortest paths in directed acyclic graphs
• Improved shortest path algorithms for nearly acyclic graphs
• scientific article; zbMATH DE number 1576683 (Why is no real title available?)
• The next‐to‐shortest path problem on directed graphs with positive edge weights
• scientific article; zbMATH DE number 1798166 (Why is no real title available?)
• An efficient algorithm to determine all shortest paths in Sierpiński graphs
• Partial Solution and Entropy
• Optimal algorithm for the nearest common dominator problem
• Optimally fast shortest path algorithms for some classes of graphs
• Shortest path algorithms for nearly acyclic directed graphs

This page was built for publication: Solving shortest paths efficiently on nearly acyclic directed graphs

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