Incremental assignment problem

Creative Commons License

Toroslu I. H., Ucoluk G.

INFORMATION SCIENCES, vol.177, no.6, pp.1523-1529, 2007 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 177 Issue: 6
  • Publication Date: 2007
  • Doi Number: 10.1016/j.ins.2006.05.004
  • Journal Name: INFORMATION SCIENCES
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.1523-1529
  • Keywords: assignment problem, weighted bipartite graph, Hungarian algorithm, ALGORITHMS, GRAPHS
  • Middle East Technical University Affiliated: Yes

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