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 条

[21] Mean analysis of an online algorithm for the vertex cover problem [J].

Birmele, Etienne ;

Delbot, Francois ;

Laforest, Christian .

INFORMATION PROCESSING LETTERS, 2009, 109 (09) :436-439

[22] SOLVING THE GENERALIZED VERTEX COVER PROBLEM BY GENETIC ALGORITHM [J].

Milanovic, Marija .

COMPUTING AND INFORMATICS, 2010, 29 (06) :1251-1265

[23] An approximation algorithm for the partial vertex cover problem in hypergraphs [J].

El Ouali, Mourad ;

Fohlin, Helena ;

Srivastav, Anand .

JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (02) :846-864

[24] An approximation algorithm for the partial vertex cover problem in hypergraphs [J].

Mourad El Ouali ;

Helena Fohlin ;

Anand Srivastav .

Journal of Combinatorial Optimization, 2016, 31 :846-864

[25] A novel algorithm for the vertex cover problem based on minimal elements of discernibility matrix [J].

Zhuang, Shengyang ;

Chen, Degang .

INTERNATIONAL JOURNAL OF MACHINE LEARNING AND CYBERNETICS, 2019, 10 (12) :3467-3474

[26] Multi-Objective Neighborhood Search Algorithm Based on Decomposition for Multi-Objective Minimum Weighted Vertex Cover Problem [J].

Hu, Shuli ;

Wu, Xiaoli ;

Liu, Huan ;

Wang, Yiyuan ;

Li, Ruizhi ;

Yin, Minghao .

SUSTAINABILITY, 2019, 11 (13)

[27] A novel algorithm for the vertex cover problem based on minimal elements of discernibility matrix [J].

Shengyang Zhuang ;

Degang Chen .

International Journal of Machine Learning and Cybernetics, 2019, 10 :3467-3474

[28] An NC1 algorithm for the persistency problem in bipartite graphs [J].

Lakhal, J ;

Litzler, L .

PARALLEL AND DISTRIBUTED COMPUTING SYSTEMS - PROCEEDINGS OF THE ISCA 9TH INTERNATIONAL CONFERENCE, VOLS I AND II, 1996, :450-455

[29] A new motion equation for the minimum vertex cover problem [J].

Xu, XS ;

Tang, Z ;

Wang, RL ;

Wang, XG .

NEUROCOMPUTING, 2004, 56 :441-446

[30] New Hybrid Genetic Algorithm for Vertex Cover Problems [J].

Huo Hongwei Xu Jin School of Computer Science Xidian University Xian P R China Department of Control Science and Engineering Huazhong University ofScience and Technology Wuhan P R China .

JournalofSystemsEngineeringandElectronics, 2003, (04) :90-94

← 1 2 3 4 5 →