دانلود مقاله ISI انگلیسی شماره 7980
عنوان فارسی مقاله

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

کد مقاله سال انتشار مقاله انگلیسی ترجمه فارسی تعداد کلمات
7980 2003 15 صفحه PDF سفارش دهید 10500 کلمه
خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
عنوان انگلیسی
Neural network-based heuristic algorithms for hypergraph coloring problems with applications
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Journal of Parallel and Distributed Computing, Volume 63, Issue 9, September 2003, Pages 786–800

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

چکیده انگلیسی

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.

خرید مقاله
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.