Incremental assignment problem

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(vertical bar V vertical bar(2)) algorithm for the problem. (c) 2006 Elsevier Inc. All rights reserved.

Citation Formats
İ. H. Toroslu and G. Üçoluk, “Incremental assignment problem,” INFORMATION SCIENCES, vol. 177, no. 6, pp. 1523–1529, 2007, Accessed: 00, 2020. [Online]. Available: