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)。