Development and Applications of Efficient Algorithms for Combinatorial Optimization Problems

(1)提出了求无向图中最大团的分支定界算法。他们成功地利用贪婪着色算法给出了最大团大小的上界。实验结果表明，该算法不仅适用于大量随机图，而且适用于DIMACS基准图。对最大团问题也提出了一种近似算法。在此基础上，提出了在加权图中求最大权团的分支定界算法。建立了一种寻找所有最大团的算法，并在实验中证明了它的有效性。(2)利用上述思想，提出了顶点着色问题的近似和精确算法。对于许多随机图和DIMACS基准图，它们被证实是非常有效的。(3)作为上述算法的扩展，提出了求解旅行商问题和RNA二级结构问题的高效算法。

(1) We have developed branch and bound algorithm for finding a maximum clique in an undirected graph. They successfully employ greedy coloring algorithms to give the upper bounds for the size of a maximum clique. The algorithms are evaluated experimentally for not only a number of random graphs but also DIMACS bench mark graphs and have been proved very efficient. An approximation algorithm is also developed for the maximum clique problem. In addition, efficient branch and bound algorithms are developed for finding a maximum weight clique in a weighted graph. An algorithm for finding all the maximal cliques are established and proved to be very efficient in experiments.(2) Approximate and exact algorithms are developed for the vertex coloring problem by employing the above mentioned ideas. They are confirmed to be very efficient for a number of random graphs and DIMACS bench mark graphs.(3) As extensions of the above algorithms, efficient algorithm are developed for the Traveling Salesman Problem, and RNA Secondary Structure Problem.