The Phoenix-based Parallel Algorithm for Constructing Extremal Graphs
- Ruijun Zheng, Yongqi Sun, Yali Wu, Rui Zhang
- Corresponding Author
- Ruijun Zheng
Available Online October 2013.
- https://doi.org/10.2991/isca-13.2013.34How to use a DOI?
- Parallel Computing, MapReduce, Phoenix, Extremal Graphs, OpenMP
- 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.
- Open Access
- This is an open access article distributed under the CC BY-NC license.
Cite this article
TY - CONF AU - Ruijun Zheng AU - Yongqi Sun AU - Yali Wu AU - Rui Zhang PY - 2013/10 DA - 2013/10 TI - The Phoenix-based Parallel Algorithm for Constructing Extremal Graphs BT - 2013 International Conference on Information Science and Computer Applications (ISCA 2013) PB - Atlantis Press SN - 1951-6851 UR - https://doi.org/10.2991/isca-13.2013.34 DO - https://doi.org/10.2991/isca-13.2013.34 ID - Zheng2013/10 ER -