Incremental assignment problem (vol 177, pg 1523, 2007)
In Toroslu and Ucoluk [I.H. Toroslu, G. Ucoluk, 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(n(2)) 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. (C) 2008 Elsevier Inc. All rights reserved.
weighted bipartite graph linear assignment problem hungarian algorithm