Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes
Keywords:Random graphs, vertex covering, greedy algorithm
AbstractWe 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.
Download data is not yet available.
How to Cite
Toman, E., & Stanek, M. (2012). Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes. COMPUTING AND INFORMATICS, 25(5), 393–404. Retrieved from https://www.cai.sk/ojs/index.php/cai/article/view/350