Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes
Eduard Toman ; Martin Stanek
Computing and Informatics, Tome 28 (2012) no. 1, / Harvested from Computing and Informatics
Text on Computing and Informatics
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.
Publié le : 2012-01-26
Classification:  Random graphs; vertex covering; greedy algorithm 
@article{cai350,
     author = {Eduard Toman and Martin Stanek},
     title = {Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes},
     journal = {Computing and Informatics},
     volume = {28},
     number = {1},
     year = {2012},
     language = {en},
     url = {http://dml.mathdoc.fr/item/cai350}
}

Eduard Toman; Martin Stanek. Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes. Computing and Informatics, Tome 28 (2012) no. 1, . http://gdmltest.u-ga.fr/item/cai350/