Open Access iconOpen Access



Vertex Cover Optimization Using a Novel Graph Decomposition Approach

Abdul Manan1, Shahida Bashir1, Abdul Majid2,*

1 Department of Mathematics, University of Gujrat, Gujrat, 50700, Pakistan
2 Department of Physics, University of Gujrat, Gujrat, 50700, Pakistan

* Corresponding Author: Abdul Majid. Email: email

Computers, Materials & Continua 2022, 73(1), 701-717.


The minimum vertex cover problem (MVCP) is a well-known combinatorial optimization problem of graph theory. The MVCP is an NP (nondeterministic polynomial) complete problem and it has an exponential growing complexity with respect to the size of a graph. No algorithm exits till date that can exactly solve the problem in a deterministic polynomial time scale. However, several algorithms are proposed that solve the problem approximately in a short polynomial time scale. Such algorithms are useful for large size graphs, for which exact solution of MVCP is impossible with current computational resources. The 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 etc. This work aims to solve the MVCP approximately by a novel graph decomposition approach. The 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 paths. In order to reduce complexity of the algorithm a new strategy is also proposed. The reduction strategy can be used for any algorithm solving MVCP. Based on the graph decomposition and the reduction strategy, two algorithms are formulated to approximately solve the MVCP. These algorithms are tested using well known standard benchmark graphs. The key feature of the results is a good approximate error ratio and improvement in optimum vertex cover values for few graphs.


Cite This Article

APA Style
Manan, A., Bashir, S., Majid, A. (2022). Vertex cover optimization using a novel graph decomposition approach. Computers, Materials & Continua, 73(1), 701-717.
Vancouver Style
Manan A, Bashir S, Majid A. Vertex cover optimization using a novel graph decomposition approach. Comput Mater Contin. 2022;73(1):701-717
IEEE Style
A. Manan, S. Bashir, and A. Majid "Vertex Cover Optimization Using a Novel Graph Decomposition Approach," Comput. Mater. Contin., vol. 73, no. 1, pp. 701-717. 2022.

cc This work is licensed under a Creative Commons Attribution 4.0 International License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
  • 1245


  • 635


  • 0


Share Link