A MapReduce Algorithm for Minimum Vertex Cover Problems and Its Randomization
DOI:
https://doi.org/10.31577/cai_2020_5_952Keywords:
MapReduce, minimum vertex cover, Hadoop, optimization, algorithm design, randomized algorithmAbstract
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
Issue
Section
Articles