The following information was submitted:
Transactions: WSEAS Transactions
Transactions ID Number: 18-104
Full Name: Laura Ciupala
Position: Associate Professor
Age: ON
Sex: Female
Address: Brasov, Iuliu Maniu Str., 50
Country: ROMANIA
Tel:
Tel prefix:
Fax:
E-mail address: laura_ciupala@yahoo.com
Other E-mails: laura.ciupala@unitbv.ro
Title of the Paper: Incremental algorithms for optimal flows in networks
Authors as they appear in the Paper: Laura Ciupala
Email addresses of all the authors: laura_ciupala@yahoo.com,laura.ciupala@unitbv.ro
Number of paper pages: 10
Abstract: In this paper, we will use incremental algorithms in order to save computational time when solving different network flow problems. We will focus on two important network flow problems: maximum flow problem and minimum cost flow problem. Incremental algorithms are appropriated to be used when we have a network in which we already have established an optimal flow (in our case either a maximum flow or a minimum cost flow), but we must modify the network by inserting a new arc or by deleting an existent arc. An incremental algorithm starts with an optimal flow in the initial network. It gradually modifies it and ends with an optimal flow in the modified network. First, we present incremental algorithms for the maximum flow problem. These algorithms were developed by S. Kumar and P. Gupta in 2003. They described algorithms for determining maximum flows in a network obtained from a given network in which a maximum flow is already known and in which a new arc is inserte!
d or an existent arc is deleted. Finally, we describe our incremental algorithms for the minimum cost flow problem. Let us consider a network in which we already established a minimum cost flow. We describe and solve the problem of establishing a minimum cost flow in this network after inserting a new arc and after deleting an existent arc. We focus on these problems because they arise in practice.
Keywords: Incremental computation, Maximum flow, Minimum cost flow, Network algorithms, Network flow.
EXTENSION of the file: .doc
Special (Invited) Session: Incremental Algorithms for the Minimum Cost Flow Problem
Organizer of the Session: 659-355
How Did you learn about congress:
IP ADDRESS: 188.24.140.95
