Variable Neighborhood Search for Extremal Graphs. 2. Finding Graphs with Extremal Energy

Variable Neighborhood Search for Extremal Graphs. 2. Finding Graphs with Extremal Energy
复制标题

DOI：
10.1021/ci9801419
复制
发表时间：
1998-08
期刊：
J. Chem. Inf. Comput. Sci.
影响因子：
--
通讯作者：
G. Caporossi;D. Cvetkovi;I. Gutman;P. Hansen
G. Caporossi;D. Cvetkovi;I. Gutman;P. Hansen
中科院分区：
其他
文献类型：
--
作者：
G. Caporossi;D. Cvetkovi;I. Gutman;P. Hansen

文献摘要

被引文献

相似文献

概述了最近发展起来的用于组合优化和全局优化的变邻域搜索(VNS)亚启发式方法，以及它对寻找关于一个或多个不变量的极图问题的专门化以及相应的程序(AGX)。我们以能量E为例说明了该算法的潜力，能量E是一个图形不变量，它(对于共轭碳氢化合物分子图)对应于总的π电子能量。AGX提出了E的新的上下界，并提出了关于E值为极值的分子图的几个猜想。此外，事实证明，大多数界限都是成立的。
The recently developed Variable Neighborhood Search (VNS) metaheuristic for combinatorial and global optimization is outlined together with its specialization to the problem of finding extremal graphs with respect to one or more invariants and the corresponding program (AGX). We illustrate the potential of the VNS algorithm on the example of energy E, a graph invariant which (in the case of molecular graphs of conjugated hydrocarbons) corresponds to the total π-electron energy. Novel lower and upper bounds for E are suggested by AGX and several conjectures concerning (molecular) graphs with extremal E values put forward. Moreover, most of the bounds are proved to hold.