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

DOI10.1023/A:1008647026576zbMATH Open0881.90121MaRDI QIDQ1360244FDOQ1360244

Authors: Betty L. Hickman, D. M. Scott 

Publication date: 17 July 1997

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

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

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)

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)