The Distributed Algorithm for Constructing Extremal Graphs without Hexagon
Rui Zhang, Yongqi Sun, Nan Zhao · International Journal of Applied Mathematics & Statistics/International journal of applied mathematics and statistics · 2014
MapReduce is a common model for processing large dataset by which the programming for distributed computing can be easier. The extremal graph is a graph with the maximum size and not containing some given subgraphs. In this paper, the distributed algorithm based on MapReduce for constructing extremal graphs is designed and implemented. Employing this algorithm, the extremal graphs not containing hexagon are constructed, which shows that the graph of order 28 and size at least 71 must contain a hexagon. Moreover, the experimental results show that average efficiency of the algorithm is 75.48%.