A subtree-partitioning algorithm for inducing parallelism in network simplex dual updates

DOI10.1023/A:1008647026576MaRDI QIDQ1360244zbMATH OpenFDO

Authors Betty L. Hickman, D. M. Scott

Publication date 17 July 1997

Published in Computational Optimization and Applications (Search for Journal in Brave)

zbMATH Keywords

multiple processesnetwork simplex basis subtreeparallel network simplex implementation

Mathematics Subject Classification ID

Parallel numerical computation (65Y05) Large-scale problems in mathematical programming (90C06) Programming involving graphs or networks (90C35) Deterministic network models in operations research (90B10)

Recommendations

• Optimal parallel algorithms for multiple updates of minimum spanning trees
• Parallel algorithm for finding a core of a tree network
• Parallel algorithms for computing maximal independent sets in trees and for updating minimum spanning trees
• An efficient parallel algorithm for updating minimum spanning trees
• A simple optimal parallel algorithm for a core of a tree
• Parallel implementation of the Ramalingam decremental algorithm for dynamic updating the single-sink shortest paths subgraph
• An efficient parallel algorithm for multiple edge updates of minimum spanning trees on sparse graphs
• Parallel Simplex for Large Pure Network Problems: Computational Testing and Sources of Speedup
• Parallel implementation of the Ramalingam incremental algorithm for dynamic updating the shortest-paths subgraph

Cited in

(2)

• The network simplex method on a multiprocessor
• Parallel arc-allocation algorithms for optimizing generalized networks

This page was built for publication: A subtree-partitioning algorithm for inducing parallelism in network simplex dual updates

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