A deficit scaling algorithm for the minimum flow problem | Zendy

Laura Ciupală | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

A deficit scaling algorithm for the minimum flow problem

Author(s) -

Laura Ciupală

Publication year - 2006

Publication title -

sadhana

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.268

H-Index - 49

eISSN - 0973-7677

pISSN - 0256-2499

DOI - 10.1007/bf02703378

Subject(s) - scaling , bottleneck , maximum flow problem , algorithm , flow (mathematics) , minimum cost flow problem , mathematics , computer science , mathematical optimization , flow network , geometry , embedded system

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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research