TY - JOUR AU - Toman, Eduard AU - Stanek, Martin PY - 2012/01/30 Y2 - 2024/03/28 TI - Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes JF - COMPUTING AND INFORMATICS JA - Comput. Inform. VL - 25 IS - 5 SE - Articles DO - UR - https://www.cai.sk/ojs/index.php/cai/article/view/350 SP - 393-404 AB - 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. ER -