Efficient parallel implementation of the Ramalingam decremental algorithm for updating the shortest paths subgraph

zbMATH Open1413.68177MaRDI QIDQ4610076FDOQ4610076

Authors: A. Sh. Nepomnyaschaya 

Publication date: 5 April 2018

Recommendations

• Parallel implementation of the Ramalingam decremental algorithm for dynamic updating the single-sink shortest paths subgraph
• Parallel implementation of the Ramalingam incremental algorithm for dynamic updating the shortest-paths subgraph
• An associative version of the Ramalingam decremental algorithm for the dynamic all-pairs shortest-path problem
• Decremental associative algorithm for updating the shortest paths tree
• Associative version of the Ramalingam incremental algorithm for the dynamic all-pairs shortest-path problem

zbMATH Keywords

adjacency matrixtime complexityassociative parallel processordecremental algorithmdirected weighted graphaccess data by contentssubgraph of the shortest paths

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Paths and cycles (05C38) Parallel algorithms in computer science (68W10)

Cited In (6)

• Parallel implementation of the Ramalingam decremental algorithm for dynamic updating the single-sink shortest paths subgraph
• Associative version of the Ramalingam incremental algorithm for the dynamic all-pairs shortest-path problem
• Decremental associative algorithm for updating the shortest paths tree
• An associative version of the Ramalingam decremental algorithm for the dynamic all-pairs shortest-path problem
• Associative parallel algorithm for dynamic update of shortest paths tree after inserting an arc
• Parallel implementation of the Ramalingam incremental algorithm for dynamic updating the shortest-paths subgraph

This page was built for publication: Efficient parallel implementation of the Ramalingam decremental algorithm for updating the shortest paths subgraph

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