شبکه عصبی مبتنی بر الگوریتم های هیوریستیک برای رنگ آمیزی مسئله گراف با برنامه های کاربردی

The graph coloring problem is a classic one in combinatorial optimization with a diverse set of significant applications in science and engineering. In this paper, we study several versions of this problem generalized to hypergraphs and develop solutions based on the neural network approach. We experimentally evaluate the proposed algorithms, as well as some conventional ones, on certain types of random hypergraphs. We also evaluate our algorithms on specialized hypergraphs arising in implementations of parallel data structures. The neural network algorithms turn out to be competitive with the conventional ones we study. Finally, we construct a family of hypergraphs that is hard for a greedy strong coloring algorithm, whereas our neural network solutions perform quite well.

The graph coloring problem is to color the vertices of an undirected graph with the fewest number of colors such that no two adjacent vertices are assigned the same color. This problem is a classic one in combinatorial optimization with a diverse set of significant applications in science and industry. In this paper we study several versions of this problem generalized onto hypergraphs. A hypergraph, like a graph, is comprised of a vertex-set V={v1,…,vn} and an edge-set E={e1,…,em}. A hypergraph differs in that a (hyper) edge is an arbitrary subset of V, not just a 2-element subset. In this paper we often deal with a restricted class of hypergraphs called d-cardinality hypergraphs in which hyperedges have cardinality at most d. Hypergraph problems often retain their theoretical and practical applications in a generalized setting. Applications of hypergraph optimization problems include course scheduling (hypergraph vertex cover); data access in parallel memory systems (hypergraph coloring); job scheduling in multiprocessor systems (hypergraph matching); and others (see [15]). The graph coloring problem may be generalized to hypergraphs in more than one way. One still wishes to assign colors to vertices in such a way that all edges are “properly” colored, but now the definition of proper is not unique. Hypergraph coloring remains a computationally challenging problem, and inherits the applications of graph coloring in a generalized setting.

In this paper we presented different coloring problems on hypergraphs. These problems arise naturally in applications involving conflict-free access of data in parallel memory systems. We considered several conventional algorithms to solve those problems and some specialized algorithms for hypergraphs arising from various data structures. We also introduced two types of neural network algorithms: primal–target, and Hopfield Net based. Our experiments showed that neural net algorithms were competitive with the conventional ones on random as well as structured hypergraphs. We have also presented a family of hypergraphs that are hard for the greedy strong coloring algorithms. Our network algorithms consistently outperformed two greedy algorithms on those hypergraphs finding optimal solutions in all cases. One greedy algorithm outperformed our neural network algorithms in all cases but one in which it did not converge. The latter algorithm however is not scalable to a large number of vertices. In our future work we would like to work on improving mappings for neural network algorithms for the strong coloring problem. We also plan to consider other specialized hypergraphs arising in different applications. other specialized hypergraphs arising in different applications.