scientific article; zbMATH DE number 1798166

MaRDI QIDQ4553236zbMATH OpenFDO

Authors Valerie King, Mikkel Thorup

Publication date 4 November 2002

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Nonnumerical algorithms (68W05)

Recommendations

• Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
• Space-efficient algorithms for reachability in directed geometric graphs
• Improving Space Efficiency With Path Length Prediction for Finding $k$ Shortest Simple Paths
• A Space-Efficient Algorithm for the Dynamic DFS Problem in Undirected Graphs
• Space-efficient DFS and applications to connectivity problems: simpler, leaner, faster
• Space-efficient fully dynamic DFS in undirected graphs
• Improved decremental algorithms for maintaining transitive closure and all-pairs shortest paths
• Solving shortest paths efficiently on nearly acyclic directed graphs
• Shortest path algorithms for nearly acyclic directed graphs

Cited in

(6)

• Fully dynamic all pairs shortest paths with real edge weights
• Design of algorithms for spatial-time reduction complexity of dynamic programming
• Implementation of a three-stage approach for the dynamic resource-constrained shortest-path sub-problem in branch-and-price
• Space-efficient algorithms for reachability in directed geometric graphs
• Dynamic shortest paths and transitive closure: algorithmic techniques and data structures
• Space saving by dynamic algebraization based on tree-depth

This page was built for publication:

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