Abdul Manan1, Shahida Bashir1, Abdul Majid2,*
CMC-Computers, Materials & Continua, Vol.73, No.1, pp. 701-717, 2022, DOI:10.32604/cmc.2022.027064
Abstract 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… More >
Login
Register
