NC algorithms for dynamically solving the all pairs shortest paths problem and related problems

DOI10.1016/0020-0190(96)00037-3zbMath0875.68507OpenAlexW1995587182MaRDI QIDQ1350623

Hong Shen, Brendan D. McKay, Weifa Liang

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00037-3

zbMATH Keywords

Parallel algorithmsPartially dynamic graph algorithmsThe all pairs shortest paths problemThe longest path problemThe transitive closure problemTopological sorting

Mathematics Subject Classification ID

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

Cites Work

• On-line computation of transitive closures of graphs
• Prallel algorithms for analyzing activity networks
• Finding paths and deleting edges in directed acyclic graphs
• Speeding up dynamic transitive closure for bounded degree graphs
• Incremental algorithms for minimal length paths
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: NC algorithms for dynamically solving the all pairs shortest paths problem and related problems