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

Authors

  • Eduard Toman
  • Martin Stanek

Keywords:

Random graphs, vertex covering, greedy algorithm

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