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 条
  • [41] A generalization of the Assignment Problem, and its application to the Rank Aggregation Problem
    Manea, Florin
    Ploscaru, Calina
    FUNDAMENTA INFORMATICAE, 2007, 81 (04) : 459 - 471
  • [42] Solving the minsum product rate variation problem as an assignment problem
    Moreno, Natalia
    Corominas, Albert
    INTERNATIONAL JOURNAL OF FLEXIBLE MANUFACTURING SYSTEMS, 2006, 18 (04): : 269 - 284
  • [43] Assignment Problem and Vehicle Routing Problem for an Improvement of Cash Distribution
    Boonsam, Prat
    Suthikarnnarunai, Nanthi
    Chitphaiboon, Whetisak
    WORLD CONGRESS ON ENGINEERING AND COMPUTER SCIENCE, WCECS 2011, VOL II, 2011, : 1160 - 1164
  • [44] Solving the minsum product rate variation problem as an assignment problem
    Natalia Moreno
    Albert Corominas
    International Journal of Flexible Manufacturing Systems, 2006, 18 : 269 - 284
  • [45] Complexity analysis of an assignment problem with controllable assignment costs and its applications in scheduling
    Yedidsion, Liron
    Shabtay, Dvir
    Kaspi, Moshe
    DISCRETE APPLIED MATHEMATICS, 2011, 159 (12) : 1264 - 1278
  • [46] Modified Balanced Assignment Problem in Vector Case: System Construction Problem
    Kamura, Yuusaku
    Nakamori, Mario
    2014 INTERNATIONAL CONFERENCE ON COMPUTATIONAL SCIENCE AND COMPUTATIONAL INTELLIGENCE (CSCI), VOL 2, 2014, : 52 - 56
  • [47] The Stochastic Location-Assignment Problem on a Tree
    Ting Zeng
    James E. Ward
    Annals of Operations Research, 2005, 136 : 81 - 97
  • [48] Fuzzy tabu search for solving the assignment problem
    Li, CG
    Yu, JB
    Liao, XF
    2002 INTERNATIONAL CONFERENCE ON COMMUNICATIONS, CIRCUITS AND SYSTEMS AND WEST SINO EXPOSITION PROCEEDINGS, VOLS 1-4, 2002, : 1151 - 1155
  • [49] Group-to-group reviewer assignment problem
    Wang, Fan
    Zhou, Shaorui
    Shi, Ning
    COMPUTERS & OPERATIONS RESEARCH, 2013, 40 (05) : 1351 - 1362
  • [50] The stochastic location-assignment problem on a tree
    Zeng, T
    Ward, JE
    ANNALS OF OPERATIONS RESEARCH, 2005, 136 (01) : 81 - 97
12345