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

Year, pages: 2006, 393 - 404

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, 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.

Toman, E., Stanek, M. 2006. Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes. In Computing and Informatics, vol. 25, no.5, pp. 393-404. 1335-9150.

Toman, E., Stanek, M. (2006). Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes. Computing and Informatics, 25(5), 393-404. 1335-9150.