An addendum on the incremental assignment problem
| Authors | |
|---|---|
| Publication date | 2008 |
| Journal | Information Sciences |
| Volume | Issue number | 178 | 23 |
| Pages (from-to) | 4583-4583 |
| Organisations |
|
| 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. |
| Document type | Article |
| Published at |
https://doi.org/10.1016/j.ins.2008.07.020
(Final published version)
|
| Permalink to this page | |