The Phoenix-based Parallel Algorithm for Constructing Extremal Graphs

DOI

10.2991/isca-13.2013.34How to use a DOI?

Keywords

Parallel Computing, MapReduce, Phoenix, Extremal Graphs, OpenMP

Abstract

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.

Copyright

© 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/).

Download article (PDF)

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  -