A MapReduce Algorithm for Minimum Vertex Cover Problems and Its Randomization

Authors

  • Morikazu Nakamura Faculty of Engineering, University of the Ryukyus, Okinawa 903-0213, Japan
  • Daiki Kinjo Faculty of Engineering, University of the Ryukyus, Okinawa 903-0213, Japan
  • Takeo Yoshida Faculty of Engineering, University of the Ryukyus, Okinawa 903-0213, Japan

DOI:

https://doi.org/10.31577/cai_2020_5_952

Keywords:

MapReduce, minimum vertex cover, Hadoop, optimization, algorithm design, randomized algorithm

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 that it demonstrates 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 good expected approximate ratio.

Downloads

Download data is not yet available.

Downloads

Published

2021-03-25

How to Cite

Nakamura, M., Kinjo, D., & Yoshida, T. (2021). A MapReduce Algorithm for Minimum Vertex Cover Problems and Its Randomization. Computing and Informatics, 39(5), 952–972. https://doi.org/10.31577/cai_2020_5_952