首页 | 本学科首页   官方微博 | 高级检索  
     


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号