The following information was submitted:
Transactions: WSEAS TRANSACTIONS ON COMPUTERS
Transactions ID Number: 27-714
Full Name: Laura Ciupala
Position: Associate Professor
Age: ON
Sex: Female
Address: Brasov, Iuliu Maniu Str., 50
Country: ROMANIA
Tel: 414016
Tel prefix: +40268
Fax: +40268414016
E-mail address: laura_ciupala@yahoo.com
Other E-mails: laura.ciupala@unitbv.ro
Title of the Paper: Sequential and parallel deficit scaling algorithms for minimum flow in bipartite networks
Authors as they appear in the Paper: Laura Ciupala Eleonor Ciurea
Email addresses of all the authors: laura_ciupala@yahoo.com,laura.ciupala@unitbv.ro,e.ciurea@unitbv.ro
Number of paper pages: 10
Abstract: In this paper, first we describe the deficit scaling algorithm for minimum flow in bipartite networks. This algorithm is obtained from the deficit scaling algorithm for minimum flow in regular networks developed by Ciupalã in [5] by replacing a pull from a node with sufficiently large deficit with two consecutive pulls. This replacement ensures that only nodes in N1 can have deficits. Consequently, the running time of the deficit scaling algorithm for minimum flow is reduced from O(nm+n2 logC) to O(n1m+n12 logC) when it is applied on bipartite networks. In the last part of this paper, we develop a parallel implementation of the deficit scaling algorithm for minimum flow in bipartite networks on an EREW PRAM. The parallel bipartite deficit scaling algorithm performs a pull from an active node with a sufficiently large deficit and with the smallest distance label from N1 at a time followed by a set of pulls from several nodes in N2 in parallel. It runs in O(n12 log !
C log p) time on an EREW PRAM with p = m/n1 processors, which is within a logarithmic factor of the running time of the sequential bipartite deficit scaling algorithm for minimum flow.
Keywords: Network flow; Network algorithms; Bipartite network; Parallel algorithms; Minimum flow problem; Scaling technique
EXTENSION of the file: .rtf
Special (Invited) Session: A parallel algorithm for the minimum flow problem in bipartite networks
Organizer of the Session: 591-244
How Did you learn about congress:
IP ADDRESS: 79.116.203.240
