An Extended Heuristic Algorithm to Settle Reacting Objects on a Planar Surface

[摘要] Graph theory is a key subject for both mathematics and computer science. It is used for modelling many problems such as maximal independent set, minimum covering and matching. In our study, we have extended the previous work on placing materials that may react with each other on a 2-D warehouse. We have modelled the problem using graph theory. Then, we have developed extensions on the heuristic algorithm which is using Paull-Unger method that finds Maximal Independent Sets. First two of these extensions include finding solutions with gaps for specific graphs, and meanwhile capability of performing replacement in any desired rectangle surface. The last and most effective extension is pruning unnecessary backtracking steps with the help of smarter heuristics in the algorithm.

[学科分类] 计算数学

[关键词] Graph Theory;Independent Set Problem;Storage Problem;Heuristic Algorithms