Brunel University Research Archive (BURA) >
University >
Publications >

Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/5899

Title: Experimental evaluation of algorithmic solutions for the maximum generalised network flow problem
Authors: Radzik, T
Yang, S
Keywords: Network optimisation
Network flow algorithms
Generalised flow
Experimental evaluation
Publication Date: 2001
Citation: Technical Report (2001/54)
Abstract: The maximum generalised network flow problem is to maximise the net flow into a specified node in a network with capacities and gain-loss factors associated with edges. In practice, input instances of this problem are usually solved using general-purpose linear programming codes, but this may change because a number of specialised combinatoria generalised-flow algorithms have been recently proposed. To complement the knwon theoretical analyses of these algorithms, we develop their implementations and investigate their actual performance. We focus in this study on Goldfarb, Jin and Orlin's excess-scaling algorithm and Tardos and Wayne's push-relabel algorithm. We develop variants of these algorithms to implementations of simple, but non-polynomial, combinatorial algorithms proposed by Onaga and Truemper, and with performance of CPLEX, a commercial general-purpose linear progamming package.
Description: Also available as Technical Report No. TR-01-09, Department of Computer Science, King's College London, UK, 2001.
Sponsorship: This work was supported by the EPSRC grant GR/L81468
URI: http://www.cs.le.ac.uk/people/sy11/Papers/TR-2001-54.pdf
http://bura.brunel.ac.uk/handle/2438/5899
Appears in Collections:Publications
Computer Science
Dept of Computer Science Research Papers

Files in This Item:

File Description SizeFormat
Fulltext.pdf322.84 kBAdobe PDFView/Open

Items in BURA are protected by copyright, with all rights reserved, unless otherwise indicated.