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 条
  • [21] Variants of the assignment problem - Worst cost minimization and vector cost assignment
    Sakakibara, S
    Kamura, Y
    Nakamori, M
    PDPTA '04: PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON PARALLEL AND DISTRIBUTED PROCESSING TECHNIQUES AND APPLICATIONS, VOLS 1-3, 2004, : 305 - 310
  • [22] DGAP - The Dynamic Generalized Assignment Problem
    Konstantin Kogan
    Avraham Shtub
    Annals of Operations Research, 1997, 69 : 227 - 239
  • [23] ON THE SOLUTION OF ONE MODIFIED ASSIGNMENT PROBLEM
    Myshkina, Irina Yurievna
    Grudtsyna, Larisa Yurievna
    Zakiev, Ilnar Azgamovich
    AD ALTA-JOURNAL OF INTERDISCIPLINARY RESEARCH, 2019, 9 (02): : 142 - 144
  • [24] Max algebra and the linear assignment problem
    Burkard, RE
    Butkovic, P
    MATHEMATICAL PROGRAMMING, 2003, 98 (1-3) : 415 - 429
  • [25] The Security Assignment Problem and Its Solution
    Longhas, Paul Ryan A.
    Abdul, Alsafat M.
    Baccay, Edcon B.
    INTERNATIONAL JOURNAL OF ANALYSIS AND APPLICATIONS, 2023, 21
  • [26] Study on relaxation algorithm of assignment problem
    Liu, Qiming
    Bai, Shu-yan
    Zhang, Fu-zeng
    General System and Control System, Vol I, 2007, : 297 - 300
  • [27] Max algebra and the linear assignment problem
    Rainer E. Burkard
    Peter Butkovič
    Mathematical Programming, 2003, 98 : 415 - 429
  • [28] Target assignment problem for air raid
    Chudy, M
    CONTROL AND CYBERNETICS, 1999, 28 (01): : 101 - 113
  • [29] Advances in Assignment Problem and Comparison of Algorithms
    Yan Chaobo
    Zhao Qianchuan
    PROCEEDINGS OF THE 27TH CHINESE CONTROL CONFERENCE, VOL 3, 2008, : 607 - 611
  • [30] An evolutionary heuristic algorithm for the assignment problem
    Ramadoss, Senthil Kumar
    Singh, Ajit Pal
    Mohiddin, Illauddin Kamaluddin Gulam
    OPSEARCH, 2014, 51 (04) : 589 - 602
12345