Optimization design for parallel coloring of a set of graphs in the High-Performance Computing

摘要

This paper presents solution to problem of edge coloring of sizable set of cubic graphs and examination of relations between these graphs. We solved this problem on various computing systems and for various sizes of the problem (various number of graphs). For the computations we used High-Performance Computing Cluster and Amazon Web Services cloud environment. We measured and analyzed time of computation of edge coloring and other properties. Largest set we worked with contained almost 10 million graphs. We created new methodology, which can be used to finding order of the edges which optimizes time of computation of edge coloring for certain subset of graphs. On the basis of this methodology, we implemented algorithm for parallel edge coloring of set of graphs. For testing of the methodology, we designed 8 experiments. Results showed, that worst time of edge coloring of graph from set of 19 935 graphs before use of the methodology was 1260 ms. After application of our methodology, we found same order of edge coloring for whole group of 19 935 graphs and the highest time of coloring was 10 ms.