Premium
An advanced dual incremental network algorithm
Author(s) -
Schmidt Stephen R.,
Jensen Paul A.,
Barnes J. Wesley
Publication year - 1982
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230120412
Subject(s) - dual (grammatical number) , computer science , code (set theory) , algorithm , arc (geometry) , mathematics , art , geometry , literature , set (abstract data type) , programming language
An extensive literature survey reveals that computational analyses of pure minimumcost‐network algorithms do not address the use of dual incremental codes. Previous studies only compare dual‐arc‐infeasible‐, primal‐dual‐, and primal‐type network codes. Of these three types, the primal method has been shown to be computationally superior to the other methods. This paper surveys the historical development of the dual incremental method up to and including the code DUALINC. Following a comprehensive description of DUALINC, a computational comparison is made with three other recently publicized codes, two primal codes and a dual‐arc‐infeasible code. The results of this comparison reveal that the new dual incremental code is much more efficient than the dual‐arc‐infeasible code and that it is competitive with the primal codes.