Incremental assignment problem

Creative Commons License

Toroslu I. H. , Ucoluk G.

INFORMATION SCIENCES, cilt.177, sa.6, ss.1523-1529, 2007 (SCI İndekslerine Giren Dergi) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 177 Konu: 6
  • Basım Tarihi: 2007
  • Doi Numarası: 10.1016/j.ins.2006.05.004
  • Sayfa Sayıları: ss.1523-1529


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.