A deficit scaling algorithm for the minimum flow problem
CIUPAL˘A LAURA
Primary Author
mixed material
bibliography
Indianapolis
Springer India, in co-publication with Indian Academy of Sciences
2006
monographic
Volume 31, Number 3
en
English
7p
Sadhana
In this paper, we develop a new preflow algorithm for the minimum
flow problem, called deficit scaling algorithm. This is a special implementation of
the generic preflow algorithm for the minimum flow problem developed by Ciurea
and Ciupal˘a earlier. The bottleneck operation in the generic preflow algorithm is
the number of noncancelling pulls. Using the scaling technique (i.e. selecting the
active nodes with sufficiently large deficits), we reduce the number of noncancelling
pulls to O(n2 log c) and obtain an O(nm + n2 log c) algorithm.
02562499
Portal Perguruan Tinggi
EJ00002
My Library
20
2010-05-20 15:24:56
2010-05-20 15:26:08
machine generated