Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes
Keywords:
Random graphs, vertex covering, greedy algorithmAbstract
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.Downloads
Download data is not yet available.
Downloads
Published
2012-01-30
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 http://147.213.75.17/ojs/index.php/cai/article/view/350
Issue
Section
Articles