The Phoenix-based Parallel Algorithm for Constructing Extremal Graphs
Ruijun Zheng, Yongqi Sun, Yali Wu, Rui Zhang · 2013
Phoenix is an implementation of MapReduce on shared memory, aiming at supporting parallel computing based on multi-core/multi-processor efficiently.The extremal graph is a graph with the maximum number of edges without some given subgraphs.In this paper, by allocating the data of tasks appropriately and setting identifiers to distinguish different tasks, a parallel algorithm is proposed and used to construct the extremal graphs without hexagon.The experimental results show that the average speedup is 7.0432 on 8-core CPU and the average efficiency is 88.04% for constructing the extremal graphs of order no more than 28.Finally, three extremal graphs of order 29 without hexagon are obtained by employing the algorithm.