Development and Evaluations of Efficient Algorithms for Combinatorial Optimization Problems

本文提出了一个求图的最大团的简单的分支定界算法。我们的方法先后适用于修剪方法的基础上贪婪着色，然后适当的安排考虑的顶点。该算法有效地减少了搜索树的节点数，因此运行速度快。实验证实，它运行速度更快的一些随机图与多达600个顶点和其他图形比几个算法已经出现在文献中。结合几种方法对该算法作了进一步的改进，并提出了一个求赋权图中最大权团的简单分支定界算法。它的边界规则主要是基于一个连续的近似着色，它已被应用于上述算法.基于玻尔兹曼机，给出了一个新的算法近似着色图。此外，将上述寻找最大权重团的算法应用于RNA二级结构预测问题。

We have developed a simple and branch and bound algorithm for finding a maximum clique of a graph. Our approach successively applies a pruning method based on greedy coloring followed by suitable arrangements for the vertices in consideration. The algorithm reduces the number of search tree nodes very effectively and hence runs fast. It is experimentally confirmed to run faster for a number of random graphs with up to 600 vertices and other graphs than several algorithms which have been appeared in the literature. This algorithm has been further improved by combining several methods.We have also developed a simple branch and bound algorithm for finding a maximum weight clique in a weighted graph. Its bounding rule is principally based upon a sequentail approximate coloring which has been applied in the above algorithms.Based upon Boltzmann machines, a new algorithm is given for approximately coloring a graph. Besides, the above algorithm for finding a maximum weight clique is applied for an RNA secondary structure prediction problem.