Variable Neighborhood Search for extremal vertices : The AutoGraphiX-III system

详细信息    查看全文

• 作者：Gilles Caporossi ^{gilles.caporossi@gerad.ca}
• 关键词：Variable neighbourhood search ; Graph theory ; Extremal graphs ; AutoGraphiX
• 刊名：Computers & Operations Research
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：78
• 期：Complete
• 页码：431-438
• 全文大小：1017 K
• 卷排序：78

文摘

AutoGraphiX is a computer aided graph theory software that was developed since 1997 (Caporossi Hansen, 2000). Its main purpose is to search for extremal graphs. This problem may be viewed as a combinatorial optimization and the Variable Neighborhood Search (VNS) metaheuristic is used to solve it. In this paper, the new system AutoGraphiX-III is presented. The main difference in this version is that is aims at studying quantities that are related to vertices instead of invariants (a single value associated to the whole graph). The problem of studying vertex related values arose from the study of complex networks (more specifically social networks). As a consequence from this new point of view is that the optimization algorithm is still based upon VNS, but was significantly changed. Beside the ability to handle vertex related values, the new algorithm may solve multi objective optimization problems. The capabilities of the new software are presented with a strong emphasis on the new VNS algorithm used for the optimization.