Please use this identifier to cite or link to this item:
Title: Dynamic trees in exterior-point Simplex-type algorithms for network flow problems
Authors: Geranis, George
Sifaleras, Angelo
Type: Article
Subjects: FRASCATI::Natural sciences::Mathematics::Applied Mathematics
FRASCATI::Natural sciences::Computer and information sciences
Keywords: Network Optimization
Computational Complexity
Data Structures
Issue Date: 2013
Publisher: Elsevier
Source: Electronic Notes in Discrete Mathematics
Volume: 41
First Page: 93
Last Page: 100
Abstract: Recently, a new Dual Network Exterior-Point Simplex Algorithm (DNEPSA) for the Minimum Cost Network Flow Problem (MCNFP) has been developed. In extensive computational studies, DNEPSA performed better than the classical Dual Network Simplex Algorithm (DNSA). In this paper, we present for the first time how to utilize the dynamic trees data structure in the DNEPSA algorithm, in order to achieve an improvement of the amortized complexity per pivot. Our work constitutes a first step towards the development of an efficient implementation of DNEPSA.
ISSN: 15710653
Other Identifiers: 10.1016/j.endm.2013.05.080
Appears in Collections:Department of Applied Informatics

Files in This Item:
File Description SizeFormat 
Dynamic trees in exterior-point Simplex-type algorithms for network flow problems.pdf124,25 kBAdobe PDFView/Open

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