A breadth first search approach for minimum vertex cover of grid graphs

摘要

The vertex cover problem is a classical graph optimization problem which remains intractable even for cubic graphs and planar graphs with maximum degree at most three. In this paper, the exact solution of the vertex cover problem is obtained for grid graphs. We introduce the breadth first search tree (bfs) technique to find the minimum vertex cover and the inverse vertex cover sets of grid graphs and prove that grids are invertible graphs. We also study the relationship between strong cover and minimum vertex cover.