A local search method based on edge age strategy for minimum vertex cover problem in massive graphs. (15th November 2021)

• Record Type: Journal Article
• Authors: Quan, Changsheng; Guo, Ping
• Is Part Of: Expert systems with applications. Volume 182(2021)
• Publication Date: 2021-11-15
• Subjects: Minimum vertex cover -- Local search algorithm -- Edge weighting -- Combinatorial optimization -- Heuristic algorithm; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2021.115185
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: For undirected graphs, the edge weighting method is simpler and more effective. A new method for using edge weights in MVCP is proposed. EAVC can find smaller vertex coverage on large real-world massive graphs. Abstract: Minimum vertex cover problem (MVC) is a classic combinatorial optimization problem, which has many critical real-life applications in scheduling, VLSI design, artificial intelligence, and network security. For MVC, researchers have proposed many heuristic algorithms, especially local search algorithms. And recently, researchers have increased their interest in solving large real-world graphs which require algorithms with faster searching performance. In this work, we propose a new edge weighting method called EABMS. EABMS has a time complexity of O(1). Based on EABMS, we propose our MVC solver framework called EAVC in solving MVC for massive graphs. We conducted experiments and compared the results of EAVC solvers with state of the art solvers. The results show that EABMS is effective in weighing edges for large sparse graphs and EAVC solvers outperform state of the art solvers.