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 等数据库收录! |
|