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个顶点和其他图的许多随机图。通过组合几种方法，我们还开发了一种简单的分支和界限算法，以在加权图中找到最大的权重集团，从而进一步改善了该算法。它的边界规则主要基于上述算法中已应用的序列近似颜色。基于Boltzmann机器，给出了一种新的算法，用于大约以图形上色。此外，在RNA二级结构预测问题上，将上述用于查找最大重量集团的算法应用。

项目成果

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

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

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

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

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

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

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

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