Please use this identifier to cite or link to this item:
https://ruomo.lib.uom.gr/handle/7000/245
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. |
URI: | https://doi.org/10.1016/j.endm.2013.05.080 https://ruomo.lib.uom.gr/handle/7000/245 |
ISSN: | 15710653 |
Other Identifiers: | 10.1016/j.endm.2013.05.080 |
Appears in Collections: | Department of Applied Informatics |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
Dynamic trees in exterior-point Simplex-type algorithms for network flow problems.pdf | 124,25 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.