Research On The Minimum Vertex Cover On The Generalized Petersen Graphs And The Circulant Graphs

Vertex Cover problem(VC) is a well-known NP-complete problems. Although the complexity of the problem is very high, it is extensively applied in the daily life. For examples, layout of the monitoring node of the large-scale network, the staff scheduling, the design of VLSI chips, etc. The main works of the paper are the following:1.Petersen graph and the circulant graph are as the research object, researching the application of branch threshold strategy of the minimum vertex cover set accurate algorithm, to calculate the minimum vertex cover problem of the large-scale figure as much as possible, to obtain the extensible structure method of the minimum vertex cover set, and summarizes its upper bound formula of the minimum vertex cover number. And then through the mathematical proof, gets its lower bounds. Using the upper and lower approximation, and ultimately determines the precise minimum vertex cover number of the graph C(n,2),C(n,3),C(n,4) and P(n,2),P(n,3).2.To see the minimum vertex cover properties of a larger networks, this article makes some preliminary research about the minimum vertex cover approximation algorithm, and the protein interaction network as the main reach object to calculate the approximate the minimum vertex cover set.3.We has set up a computational experiment platform for the minimum vertex cover problem, which can lay the foundation for the team continues to research the minimum vertex cover and related problems, including data import, algorithm experiment and graphical display, etc.