An addendum on the incremental assignment problem |
| |
Authors: | A Volgenant |
| |
Affiliation: | Operations Research Group, Faculty of Economics and Econometrics, University of Amsterdam, Roetersstraat 11, 1018 WB Amsterdam, The Netherlands |
| |
Abstract: | In Toroslu and Üçoluk I.H. Toroslu, G. Üçoluk, Incremental assignment problem, Information Sciences 177 (2007) 1523-1529] the incremental assignment problem is defined as follows. A new pair of vertices and their incident edges are added to a weighted bipartite graph whose maximum-weighted matching is already known, and the maximum-weighted matching of the extended graph is sought. An O(n2) algorithm for the problem has been derived, with n the size of a partition in the bipartite graph. We point out that such a result can be found in literature. |
| |
Keywords: | Linear assignment problem Weighted bipartite graph Hungarian algorithm |
本文献已被 ScienceDirect 等数据库收录! |
|