The Phoenix-based Parallel Algorithm for Constructing Extremal Graphs
- 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.
- © 2013, the Authors. Published by Atlantis Press.
- Open Access
- This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).
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 - Proceedings of 2013 International Conference on Information Science and Computer Applications PB - Atlantis Press SP - 196 EP - 201 SN - 1951-6851 UR - https://doi.org/10.2991/isca-13.2013.34 DO - 10.2991/isca-13.2013.34 ID - Zheng2013/10 ER -