A new efficient algorithm for weighted vertex cover in bipartite graphs based on a dual problem

被引：3
|
作者：
Zhang Yujiao [1 ]
Duan Xia [1 ]
Yue Xuerong [1 ]
Chen Zhibin [1 ]
机构：
[1] Kunming Univ Sci & Technol, Dept Math, Fac Sci, Kunming, Yunnan, Peoples R China
来源：
2018 NINTH INTERNATIONAL CONFERENCE ON INFORMATION TECHNOLOGY IN MEDICINE AND EDUCATION (ITME 2018) | 2018年
基金：
中国国家自然科学基金;
关键词：
matching; vertex cover; edge packing; polynomial time algorithm; dual problem;
D O I：
10.1109/ITME.2018.00016
中图分类号：
TP39 [计算机的应用];
学科分类号：
081203 ; 0835 ;
摘要：
The (un-weighted) vertex cover problem in general graphs is a classical NP-hard problem, but it is polynomial time solvable in bipartite graphs. This paper considers two combinatorial optimization problems. One is the weighted vertex cover problem and the other is the so-called maximum edge packing problem. We proved that in bipartite graphs, maximum edge packing problem can be viewed as the dual of the weighted vertex cover problem, and hence these two problems are polynomial time solvable. We explored the relationships between these two problems in bipartite graphs and some structural results are obtained accordingly. Furthermore, a new efficient algorithm for the weighted vertex cover problem in bipartite graphs is also derived. Our method generalized some previous algorithms for un-weighted vertex cover in bipartite graphs.
引用
收藏
页码：20 / 23
页数：4
相关论文
共 50 条
  • [1] An efficient exact algorithm for constraint bipartite vertex cover
    Fernau, H
    Niedermeier, R
    JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2001, 38 (02): : 374 - 410
  • [2] The maximum vertex coverage problem on bipartite graphs
    Apollonio, Nicola
    Simeone, Bruno
    DISCRETE APPLIED MATHEMATICS, 2014, 165 : 37 - 48
  • [3] KOSZULNESS OF VERTEX COVER ALGEBRAS OF BIPARTITE GRAPHS
    Rinaldo, Giancarlo
    COMMUNICATIONS IN ALGEBRA, 2011, 39 (07) : 2249 - 2259
  • [4] A New Approximation Algorithm for Vertex Cover Problem
    Dahiya, Sonika
    2013 INTERNATIONAL CONFERENCE ON MACHINE INTELLIGENCE AND RESEARCH ADVANCEMENT (ICMIRA 2013), 2013, : 472 - 478
  • [5] An efficient simulated annealing algorithm for the minimum vertex cover problem
    Xu, XS
    Ma, J
    NEUROCOMPUTING, 2006, 69 (7-9) : 913 - 916
  • [6] PARTIAL VERTEX COVER AND BUDGETED MAXIMUM COVERAGE IN BIPARTITE GRAPHS
    Caskurlu, Bugra
    Mkrtchyan, Vahan
    Parekh, Ojas
    Subramani, K.
    SIAM JOURNAL ON DISCRETE MATHEMATICS, 2017, 31 (03) : 2172 - 2184
  • [7] d-Transversals of stable sets and vertex covers in weighted bipartite graphs
    Bentz, C.
    Costa, M. -C.
    Picouleau, C.
    Ries, B.
    de Werrae, D.
    JOURNAL OF DISCRETE ALGORITHMS, 2012, 17 : 95 - 102
  • [8] Constrained minimum vertex cover in bipartite graphs: complexity and parameterized algorithms
    Chen, H
    Kanj, IA
    JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2003, 67 (04) : 833 - 847
  • [9] Crown reductions for the minimum weighted vertex cover problem
    Chlebik, Miroslav
    Chlebikkova, Janka
    DISCRETE APPLIED MATHEMATICS, 2008, 156 (03) : 292 - 312
  • [10] On the parameterized vertex cover problem for graphs with perfect matching
    WANG JianXin
    LI WenJun
    LI ShaoHua
    CHEN JianEr
    ScienceChina(InformationSciences), 2014, 57 (07) : 105 - 116
12345