More efficient parallel flow algorithms

descriptionPublicationkeyboard_double_arrow_right Part of book or chapter of book , Conference object , Article 01 Jan 1995 Germany Publisher:Springer Berlin Heidelberg

Authors: Dedorath, Jürgen; Gergov, Jordan; Hagerup, Torben;

doi: 10.1007/bfb0015428

handle: 11858/00-001M-0000-0014-ACA1-8

More efficient parallel flow algorithms

- Summary
- Metrics

Abstract

We develop an arsenal of tools for improving the efficiency of parallel algorithms for network-flow problems and apply it to a maximum-flow algorithm of Goldberg, a blocking-flow algorithm of Shiloach and Vishkin, and a maximum-flow algorithm of Ahuja and Orlin. Depending on the exact model of computation and the time available for the computation, we achieve a polylogarithmic reduction in the time-processor product. In particular, this leads to the first parallel implementations with optimal speedup of the corresponding sequential algorithms.

Country

Germany

Related Organizations

Max Planck Society
Germany
Max Planck Institute for Informatics
Germany
Universität Augsburg
Germany

Impact byBIP!

	selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	0
	popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.	Average
	influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).	Average
	impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.	Average