Proceedings of 2013 International Conference on Information Science and Computer Applications

The Phoenix-based Parallel Algorithm for Constructing Extremal Graphs

Authors
Ruijun Zheng, Yongqi Sun, Yali Wu, Rui Zhang
Corresponding Author
Ruijun Zheng
Available Online October 2013.
DOI
https://doi.org/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.
Open Access
This is an open access article distributed under the CC BY-NC license.

Download article (PDF)

Proceedings
2013 International Conference on Information Science and Computer Applications (ISCA 2013)
Part of series
Advances in Intelligent Systems Research
Publication Date
October 2013
ISBN
978-90786-77-85-7
ISSN
1951-6851
DOI
https://doi.org/10.2991/isca-13.2013.34How to use a DOI?
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  -