Publikationsansicht

On Implementing Push-Relabel Method For The Maximum Flow Problem (1994)

Abstract

. We study efficient implementations of the push-relabel method for the maximum flow problem. The resulting codes are faster than the previous codes, and much faster on some problem families. The speedup is due to the combination of heuristics used in our implementation. We also exhibit a family of problems for which all known methods seem to have almost quadratic time growth rate. Andrew V. Goldberg was supported in part by NSF Grant CCR-9307045 and a grant from Powell Foundation. This work was done while Boris V. Cherkassky was visiting Stanford University Computer Science Department and supported by the above-mentioned NSF and Powell Foundation grants. 1 1. Introduction The maximum flow problem is a classical combinatorial problem that comes up in a wide variety of applications. In this paper we study implementations of the push-relabel [13, 17] method for the problem. The basic methods for the maximum flow problem include the network simplex method of Dantzig [6, 7], the augmen...

Details der Publikation

Download	http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.55.8089
Quelle	ftp://theory.stanford.edu/pub/goldberg/stan-cs-tr-94-1523.ps.Z
Mitarbeiter	CiteSeerX
Archiv	CiteSeerX - Scientific Literature Digital Library and Search Engine (United States)
Typ	text
Sprache	Englisch
Verknüpfungen	10.1.1.91.1599, 10.1.1.69.9298, 10.1.1.23.7975, 10.1.1.118.2575, 10.1.1.3.2000, 10.1.1.21.1744, 10.1.1.98.8513, 10.1.1.86.1026, 10.1.1.37.3265, 10.1.1.10.5703, 10.1.1.33.5031, 10.1.1.34.5710, 10.1.1.26.6633, 10.1.1.103.6592, 10.1.1.54.4221, 10.1.1.107.1190, 10.1.1.1.2449, 10.1.1.133.3622, 10.1.1.57.4735, 10.1.1.45.3612, 10.1.1.4.8969, 10.1.1.103.8798, 10.1.1.107.3865, 10.1.1.21.7761, 10.1.1.83.5271, 10.1.1.14.5806, 10.1.1.90.1068, 10.1.1.58.2444, 10.1.1.5.8896, 10.1.1.60.4587, 10.1.1.7.4166, 10.1.1.89.3616, 10.1.1.117.9986, 10.1.1.130.4737, 10.1.1.6.1298, 10.1.1.86.8913, 10.1.1.128.6152, 10.1.1.33.3089, 10.1.1.22.1584, 10.1.1.21.8840, 10.1.1.106.1111, 10.1.1.11.1979, 10.1.1.61.695, 10.1.1.87.7370, 10.1.1.122.7945, 10.1.1.42.5774, 10.1.1.7.1543, 10.1.1.100.5306, 10.1.1.100.7007, 10.1.1.103.9348, 10.1.1.105.4485, 10.1.1.29.8723, 10.1.1.69.6748, 10.1.1.75.8219, 10.1.1.77.7584, 10.1.1.80.5682, 10.1.1.80.8483, 10.1.1.83.187, 10.1.1.84.6006, 10.1.1.85.4560, 10.1.1.86.4542, 10.1.1.86.7295, 10.1.1.87.8025, 10.1.1.133.4862, 10.1.1.89.234, 10.1.1.89.7421, 10.1.1.90.7809, 10.1.1.91.321, 10.1.1.92.8970, 10.1.1.93.6607, 10.1.1.95.887, 10.1.1.15.8804, 10.1.1.112.2877, 10.1.1.116.1195, 10.1.1.118.8118, 10.1.1.120.5974, 10.1.1.120.9884, 10.1.1.122.2298, 10.1.1.124.4432, 10.1.1.125.118, 10.1.1.125.2483, 10.1.1.126.6660, 10.1.1.129.2408, 10.1.1.132.334, 10.1.1.135.6673, 10.1.1.48.5094, 10.1.1.45.6662, 10.1.1.37.62, 10.1.1.12.9997, 10.1.1.15.7278, 10.1.1.2.2477, 10.1.1.4.2055, 10.1.1.5.8410, 10.1.1.60.6159