Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes.
Eduard Toman, Martin Staněk · 2006
Abstract. 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 [9], 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.