caa a22 4500 465774253 CHVBK 20180323111937.0 cr unu---uuuuu 170327e19901201xx s 000 0 eng 10.1007/BF02023051 doi (NATIONALLICENCE)springer-10.1007/BF02023051 Parallel arc-allocation algorithms for optimizing generalized networks [Elektronische Daten] [R. Clark, R. Meyer] Two parallel shared-memory algorithms are presented for the optimization of generalized networks. These algorithms are based on the allocation of arc-related operations in the (generalized) network simplex method. One method takes advantage of the multi-tree structure of basic solutions and performs pivot operations in parallel, utilizing locking to ensure correctness. The other algorithm utilizes only one processor for sequential pivoting, but parallelizes the pricing operation and overlaps this task with pivoting in a speculative manner (i.e. since pivoting and pricing involve data dependencies, a candidate for flow change generated by the pricing processors is not guaranteed to be acceptable, but in practice generally has this property). The relative performance of these two methods (on the Sequent Symmetry S81 multiprocessor) is compared and contrasted with that of a fast sequential algorithm on a set of large-scale test problems of up to 1,000,000 arcs. J.C. Baltzer AG, Scientific Publishing Company, 1990 Clark R. Computer Sciences Department and Center for the Mathematical Sciences, The University of Wisconsin-Madison, 53706, Madison, Wisconsin, USA aut Meyer R. Computer Sciences Department and Center for the Mathematical Sciences, The University of Wisconsin-Madison, 53706, Madison, Wisconsin, USA aut Annals of Operations Research Baltzer Science Publishers, Baarn/Kluwer Academic Publishers 22/1(1990-12-01), 129-160 0254-5330 22:1<129 1990 22 10479 https://doi.org/10.1007/BF02023051 text/html Onlinezugriff via DOI 1 research-article jats NATIONALLICENCE 856 40 https://doi.org/10.1007/BF02023051 text/html Onlinezugriff via DOI NATIONALLICENCE 700 1- Clark R. Computer Sciences Department and Center for the Mathematical Sciences, The University of Wisconsin-Madison, 53706, Madison, Wisconsin, USA aut NATIONALLICENCE 700 1- Meyer R. Computer Sciences Department and Center for the Mathematical Sciences, The University of Wisconsin-Madison, 53706, Madison, Wisconsin, USA aut NATIONALLICENCE 773 0- Annals of Operations Research Baltzer Science Publishers, Baarn/Kluwer Academic Publishers 22/1(1990-12-01), 129-160 0254-5330 22:1<129 1990 22 10479 Metadata rights reserved Springer special CC-BY-NC licence nationallicence BK010053 XK010053 XK010000 NATIONALLICENCE NATIONALLICENCE NL-springer