Incremental assignment problem

Creative Commons License

Toroslu I. H., Ucoluk G.

INFORMATION SCIENCES, cilt.177, sa.6, ss.1523-1529, 2007 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 177 Sayı: 6
  • Basım Tarihi: 2007
  • Doi Numarası: 10.1016/j.ins.2006.05.004
  • Dergi Adı: INFORMATION SCIENCES
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.1523-1529
  • Anahtar Kelimeler: assignment problem, weighted bipartite graph, Hungarian algorithm, ALGORITHMS, GRAPHS
  • Orta Doğu Teknik Üniversitesi Adresli: Evet

Özet

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.