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 citeS72, 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.
Keywords
Cite this article
@article{cai-1568,
author = {Eduard Toman and Martin Stanek},
title = {Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes},
journal = {Computing and Informatics},
volume = {25},
number = {5},
pages = {393--404},
year = {2006},
issn = {1335-9150},
url = {https://cai.type.sk/content/2006/5/analysis-of-greedy-algorithm-for-vertex-covering-of-random-graph-by-cubes/}
}
TY - JOUR AU - Eduard Toman AU - Martin Stanek TI - Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes JO - Computing and Informatics VL - 25 IS - 5 SP - 393 EP - 404 PY - 2006 SN - 1335-9150 UR - https://cai.type.sk/content/2006/5/analysis-of-greedy-algorithm-for-vertex-covering-of-random-graph-by-cubes/ KW - Random graphs KW - vertex covering KW - greedy algorithm ER -
Toman, E., & Stanek, M. (2006). Analysis of Greedy Algorithm for Vertex Covering of Random Graph by Cubes. Computing and Informatics, 25(5), 393–404. https://cai.type.sk/content/2006/5/analysis-of-greedy-algorithm-for-vertex-covering-of-random-graph-by-cubes/