.png){kind=icon}
返回
An adaptive, multiple restarts neural network algorithm for graph coloring
.png){kind=icon}
PRE
AI
DOI：10.1016/0377-2217(96)00043-4.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The graph coloring problem is amongst the most difficult ones in combinatorial optimization, with a diverse set of significant applications in science and industry. Previous neural network attempts at coloring graphs have not worked well. In particular, they do not scale up to large graphs. Furthermore, experimental evaluations on real-world graphs have been lacking, and so have comparisons with state of the art conventional algorithms. In this paper we address all of these issues. We develop an improved neural network algorithm for graph coloring that scales well with graph size. The algorithm employs multiple restarts, and adaptively reduces the network's size from restart to restart as it learns better ways to color a given graph. Hence it gets faster and leaner as it evolves. We evaluate this algorithm on a structurally diverse set of graphs that arise in different applications. We compare its performance with that of a state of the art conventional algorithm on identical graphs. The conventional algorithm works better overall, though ours is not far behind. Ours works better on some graphs. The inherent parallel and distributed nature of our algorithm, especially within a neural network architecture, is a potential advantage for implementation and speed up.
Keyword:
SCHEDULING PROBLEMS
OPTIMIZATION
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
6
论文数:
2.2W
被引数:
6.4W
机构
暂无机构信息
引用论文
Effect of volume fiber and crack length on interlaminar fracture properties of glass fiber reinforced polyester composites (GF/PO composites).png)
Mechanics
OAAI
MechanicsIF0
OAAI分享收藏Genetic Diversity and Host Specificity of Fungal Endophyte Taxa in Fescue Pasture GrassesCrop Science
Crop ScienceIF0
PREAI
分享收藏
查看更多内容