Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
396339 | Information Sciences | 2007 | 7 Pages |
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)O(|V|2) algorithm for the problem.
Related Topics
Physical Sciences and Engineering
Computer Science
Artificial Intelligence
Authors
Ismail H. Toroslu, Göktürk Üçoluk,