Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes

keywords: Random graphs, vertex covering, greedy algorithm
We study randomly induced subgraphs G of a hypercube. Specifically, we investigate vertex covering of G by cubes. We instantiate a greedy algorithm for this problem from general hypergraph covering algorithm citeS72, and estimate the length of vertex covering of G. In order to obtain this result, a number of theoretical parameters of randomly induced subgraph G were estimated.
reference: Vol. 25, 2006, No. 5, pp. 393–404