Incremental assignment problem

被引：26
|
作者：
Toroslu, Ismail H. [1 ]
Ucoluk, Gokturk [1 ]
机构：
[1] Middle E Tech Univ, Dept Comp Engn, TR-06531 Ankara, Turkey
来源：
INFORMATION SCIENCES | 2007年 / 177卷 / 06期
关键词：
assignment problem; weighted bipartite graph; Hungarian algorithm;
D O I：
10.1016/j.ins.2006.05.004
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
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.
引用
收藏
页码：1523 / 1529
页数：7
相关论文
共 50 条
  • [1] An addendum on the incremental assignment problem
    Operations Research Group, Faculty of Economics and Econometrics, University of Amsterdam, Roetersstraat 11, 1018 WB Amsterdam, Netherlands
    Information Sciences, 2008, 178 (23) : 4583
  • [2] Incremental assignment problem (vol 177, pg 1523, 2007)
    Volgenant, A.
    INFORMATION SCIENCES, 2008, 178 (23) : 4583 - 4583
  • [3] CERTAIN EXPECTED VALUES IN THE RANDOM ASSIGNMENT PROBLEM
    LAZARUS, AJ
    OPERATIONS RESEARCH LETTERS, 1993, 14 (04) : 207 - 214
  • [4] Sparse Clustered Neural Networks for the Assignment Problem
    Medjkouh, Said
    Xue, Bowen
    Hacene, Ghouthi Boukli
    COGNITIVE 2017: THE NINTH INTERNATIONAL CONFERENCE ON ADVANCED COGNITIVE TECHNOLOGIES AND APPLICATIONS, 2017, : 69 - 75
  • [5] The assignment problem revisited
    Carlos A. Alfaro
    Sergio L. Perez
    Carlos E. Valencia
    Marcos C. Vargas
    Optimization Letters, 2022, 16 : 1531 - 1548
  • [6] The assignment problem revisited
    Alfaro, Carlos A.
    Perez, Sergio L.
    Valencia, Carlos E.
    Vargas, Marcos C.
    OPTIMIZATION LETTERS, 2022, 16 (05) : 1531 - 1548
  • [7] Assignment problem with conflicts
    Oncan, Temel
    Suyak, Zeynep
    Akyuz, M. Hakan
    Altinel, I. Kuban
    COMPUTERS & OPERATIONS RESEARCH, 2019, 111 : 214 - 229
  • [8] On a variant of assignment problem
    Dong, JQ
    Li, CQ
    PROCEEDINGS OF 2002 INTERNATIONAL CONFERENCE ON MANAGEMENT SCIENCE & ENGINEERING, VOLS I AND II, 2002, : 535 - 538
  • [9] The dominance assignment problem
    Calvillo, Gilberto
    Romero, David
    DISCRETE OPTIMIZATION, 2012, 9 (03) : 149 - 158
  • [10] An extended assignment problem considering multiple inputs and outputs
    Chen, Liang-Hsuan
    Lu, Hai-Wen
    APPLIED MATHEMATICAL MODELLING, 2007, 31 (10) : 2239 - 2248
12345