Vertex Cover Optimization Using a Novel Graph Decomposition Approach
作者机构：Department of MathematicsUniversity of GujratGujrat50700Pakistan Department of PhysicsUniversity of GujratGujrat50700Pakistan
出 版 物：《Computers, Materials & Continua》 (计算机、材料和连续体（英文）)
年 卷 期：2022年第73卷第10期
页 面：701-717页
核心收录：
学科分类：07[理学] 0701[理学-数学] 070101[理学-基础数学]
主 题：Combinatorial optimization graph theory minimum vertex cover problem maximum independent set maximum degree greedy approach approximation algorithms benchmark instances
摘 要：The minimum vertex cover problem(MVCP)is a well-known combinatorial optimization problem of graph *** MVCP is an NP(nondeterministic polynomial)complete problem and it has an exponential growing complexity with respect to the size of a *** algorithm exits till date that can exactly solve the problem in a deterministic polynomial time ***,several algorithms are proposed that solve the problem approximately in a short polynomial time *** algorithms are useful for large size graphs,for which exact solution of MVCP is impossible with current computational *** MVCP has a wide range of applications in the fields like bioinformatics,biochemistry,circuit design,electrical engineering,data aggregation,networking,internet traffic monitoring,pattern recognition,marketing and franchising *** work aims to solve the MVCP approximately by a novel graph decomposition *** decomposition of the graph yields a subgraph that contains edges shared by triangular edge structures.A subgraph is covered to yield a subgraph that forms one or more Hamiltonian cycles or *** order to reduce complexity of the algorithm a new strategy is also *** reduction strategy can be used for any algorithm solving *** on the graph decomposition and the reduction strategy,two algorithms are formulated to approximately solve the *** algorithms are tested using well known standard benchmark *** key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.
维普期刊数据库