Incremental assignment problem |
| |
| Authors: | Ismail H Toroslu |
| |
| Affiliation: | Department of Computer Engineering, Middle East Technical University, METU, 06531 Ankara, Turkey |
| |
| Abstract: | In this paper we introduce the incremental assignment problem. In this problem, 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. We propose an O(|V|2) algorithm for the problem. |
| |
| Keywords: | Assignment problem Weighted bipartite graph Hungarian algorithm |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
