Development and Evaluations of Efficient Algorithms for Combinatorial Optimization Problems

组合优化问题的高效算法的开发和评估

• 批准号: 06680311
• 负责人: TOMITA Etsuji
• 金额: $ 1.41万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1994
• 资助国家: 日本
• 起止时间: 1994 至 1995
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-06680311/
• 关键词: combinatorial optimization; algorithm; maximum clique; maximum weight clique; branch-and-bound; approximate coloring; Boltzmann machine; RNA secondary structure prediction; ポルツマンマシン; 深さ優先探索; 確立アルゴリズム; RNA 2次構造予測

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.

我们开发了一种简单的分支定界算法来查找图的最大团。我们的方法相继应用了基于贪婪着色的修剪方法，然后对所考虑的顶点进行适当的安排。该算法非常有效地减少了搜索树节点的数量，因此运行速度很快。经实验证实，对于一些多达 600 个顶点的随机图和其他图，它比文献中出现的几种算法运行得更快。通过结合多种方法，该算法得到了进一步改进。我们还开发了一种简单的分支定界算法，用于在加权图中查找最大权重团。其边界规则主要基于顺序近似着色，该近似着色已应用于上述算法中。基于玻尔兹曼机，给出了一种新的图近似着色算法。此外，上述寻找最大权重团的算法应用于RNA二级结构预测问题。

项目成果

富田悦次(分担): "アルゴリズム辞典" 共立出版, 951 (1994)

富田悦司（贡献者）：《算法词典》Kyoritsu Shuppan，951 (1994)

菊池 淳: "グラフの近似彩色を行う確率アルゴリズム" 情報処理学会第52回全国大会講演論文集. (1). 67-68 (1996)

Jun Kikuchi：“图形近似着色的随机算法”第 52 届日本信息处理学会全国会议论文集 (1) (1996)。

TOMITA,Etsuji: "A simple and efficient branch and bound algorithm for finding a maximum clique with the experimental evaluations" Trans.IEICE. J79-D-I. 1-8 (1996)

TOMITA、Etsuji：“一种简单高效的分支定界算法，用于通过实验评估找到最大团” Trans.IEICE。

富田,悦次: "最大クリークを抽出する単純で効率的な分枝限定アルゴリズムと実験的評価" 電子情報通信学会論文誌. J79-D-I. 1-8 (1996)

Tomita，Etsuji：“用于提取最大派系和实验评估的简单高效的分支定界算法”，电子、信息和通信工程师学会汇刊 J79-D-I (1996)。

若月,光夫: "最大重みクリーク抽出アルゴリズムのRNAの二次構造予測への適用" 情報処理学会第52回全国大会講演論文集. (1). 53- (1996)

Wakatsuki, Mitsuo：“最大权重团提取算法在 RNA 二级结构预测中的应用”第 52 届日本信息处理学会全国会议论文集 (1)。