The Approximation Algorithm And Application Of The Minimum Vertex Cover Problem

Given an undirected graph ?EVG),( with a vertex set V and an edge set E, the minimum vertex cover problem is to find a smallest subset VS ? such that for each edge vu),( in G Su ? or Sv?, S is said to be the minimum vertex cover of G.The minimum vertex cover problem is a classic graph optimization problem. It is well known that it is an NP-complete problem. Because this problem has many important practical applications, so it is more concerned problem. So far many approximation algorithms have been presented to solve the problem, but many people are still working on it to seek a more concise and more accurate algorithm.In the paper, we study the minimum vertex cover problem by utilizing the ant colony algorithm and Dijkstra algorithm. The main contents of this paper are as follows:(1) Based on the short-circuit algorithm, respectively studies the minimum point covering problem of no right figure and empowerment figure, and design the algorithm.At first,optionally a vertex as the initial vertex in a given graph, giving an permitted set and definitions. Then, use the classical Dijkstra algorithm to search for the shortest path of the initial point to the each vertex of permitted set, further more, getting the vertex cover in accordance with certain principles. In the end, an example is given to illustrate the process rationality and validity of the algorithm.(2) About ant colony algorithm, studies the minimum point covering problem of the empowerment figure.Giving a algorithm based upon the Ant Colony Optimization(ACO)approach, to find approximate solutions to the minimum weight vertex cover problem. By modifying the state transition probability formula and strengthening initiative of the ant, The corresponding mathematical model is established, get an approximation algorithm process of seeking the minimum vertex cover. At last, an example is solved and analysised by using the method.(3) The minimum vertex cover problem is applied to solve the parking planning problem.The problem of parking planning is solved by using the approximation algorithm of the minimum vertex cover problem which have obtained, and give an optimal soluting of parking planning model.