Abstract

MapReduce is a programming paradigm for large-scale distributed information processing. This paper proposes a MapReduce algorithm for the minimum vertex cover problem, which is known to be NP-hard. The MapReduce algorithm can efficiently obtain a minimal vertex cover in a small number of rounds. We show the effectiveness of the algorithm through experimental evaluation and comparison with exact and approximate algorithms which demonstrates a high quality in a small number of MapReduce rounds. We also confirm from experimentation that the algorithm has good scalability allowing high-quality solutions under restricted computation times due to increased graph size. Moreover, we extend our algorithm to randomized one to obtain a good expected approximate ratio.

Keywords

Cite this article

@article{cai-5080,
  author  = {Morikazu Nakamura and Daiki Kinjo and Takeo Yoshida},
  title   = {A MapReduce Algorithm for Minimum Vertex Cover Problems and Its Randomization},
  journal = {Computing and Informatics},
  volume  = {39},
  number  = {5},
  pages   = {952--972},
  year    = {2020},
  issn    = {1335-9150},
  doi     = {10.31577/cai_2020_5_952}
}
Download .bib