Development and Evaluations of Efficient Algorithms for Combinatorial Optimization Problems

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

基本信息

  • 批准号:
    06680311
  • 负责人:
  • 金额:
    $ 1.41万
  • 依托单位:
  • 依托单位国家:
    日本
  • 项目类别:
    Grant-in-Aid for General Scientific Research (C)
  • 财政年份:
    1994
  • 资助国家:
    日本
  • 起止时间:
    1994 至 1995
  • 项目状态:
    已结题

项目摘要

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二级结构预测问题。

项目成果

期刊论文数量(36)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
富田悦次(分担): "アルゴリズム辞典" 共立出版, 951 (1994)
富田悦司(贡献者):《算法词典》Kyoritsu Shuppan,951 (1994)
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
菊池 淳: "グラフの近似彩色を行う確率アルゴリズム" 情報処理学会第52回全国大会講演論文集. (1). 67-68 (1996)
Jun Kikuchi:“图形近似着色的随机算法”第 52 届日本信息处理学会全国会议论文集 (1) (1996)。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
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。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
富田,悦次: "最大クリークを抽出する単純で効率的な分枝限定アルゴリズムと実験的評価" 電子情報通信学会論文誌. J79-D-I. 1-8 (1996)
Tomita,Etsuji:“用于提取最大派系和实验评估的简单高效的分支定界算法”,电子、信息和通信工程师学会汇刊 J79-D-I (1996)。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
若月,光夫: "最大重みクリーク抽出アルゴリズムのRNAの二次構造予測への適用" 情報処理学会第52回全国大会講演論文集. (1). 53- (1996)
Wakatsuki, Mitsuo:“最大权重团提取算法在 RNA 二级结构预测中的应用”第 52 届日本信息处理学会全国会议论文集 (1)。
  • DOI:
  • 发表时间:
  • 期刊:
  • 影响因子:
    0
  • 作者:
  • 通讯作者:
{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

数据更新时间:{{ journalArticles.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ monograph.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ sciAawards.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ conferencePapers.updateTime }}

{{ item.title }}
  • 作者:
    {{ item.author }}

数据更新时间:{{ patent.updateTime }}

TOMITA Etsuji其他文献

GFR推算式(eGFRcreatとeGFRcys)の臨床的意義
GFR 估算公式(eGFRcreat 和 eGFRcys)的临床意义
  • DOI:
  • 发表时间:
    2014
  • 期刊:
  • 影响因子:
    0
  • 作者:
    TOMITA Etsuji;MATSUZAKI Sora;NAGAO Atsuki;ITO Hiro;and WAKATSUKI Mitsuo;堀尾 勝
  • 通讯作者:
    堀尾 勝
ARにおけるバブルカーソルを用いた視線入力に関する検討
AR中气泡光标注视输入研究
  • DOI:
  • 发表时间:
    2022
  • 期刊:
  • 影响因子:
    0
  • 作者:
    KANAHARA Kazuho;KATAYAMA Kengo;TOMITA Etsuji;藤原智宏,金成慧,佐藤美恵
  • 通讯作者:
    藤原智宏,金成慧,佐藤美恵
Speeding-Up Construction Algorithms for the Graph Coloring Problem
图着色问题的加速构建算法

TOMITA Etsuji的其他文献

{{ item.title }}
{{ item.translation_title }}
  • DOI:
    {{ item.doi }}
  • 发表时间:
    {{ item.publish_year }}
  • 期刊:
  • 影响因子:
    {{ item.factor }}
  • 作者:
    {{ item.authors }}
  • 通讯作者:
    {{ item.author }}

{{ truncateString('TOMITA Etsuji', 18)}}的其他基金

Much faster algorithms for finding maximum and maximal cliques and their applications
用于查找最大和最大派系的更快算法及其应用
  • 批准号:
    25330009
  • 财政年份:
    2013
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Development of efficient algorithms for finding a maximum clique with theoretical and experimental evaluations and their applications
通过理论和实验评估及其应用开发寻找最大团的有效算法
  • 批准号:
    22500009
  • 财政年份:
    2010
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Improvement and extension of maximum-clique-finding algorithms with complexity analysis and their applications
复杂度分析最大团查找算法的改进和扩展及其应用
  • 批准号:
    19500010
  • 财政年份:
    2007
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Studies on Efficient Learning Algorithms from Examples
高效学习算法的实例研究
  • 批准号:
    13680435
  • 财政年份:
    2001
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Development and Applications of Efficient Algorithms for Combinatorial Optimization Problems
组合优化问题高效算法的开发与应用
  • 批准号:
    09680331
  • 财政年份:
    1997
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
Development and Evaluations of Efficient Algorithms for Finding a Maximum Clique Based upon Nueral Networks
基于神经网络寻找最大团的高效算法的开发和评估
  • 批准号:
    02650261
  • 财政年份:
    1990
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Grant-in-Aid for General Scientific Research (C)

相似国自然基金

热力耦合方程组的并行多尺度算法
  • 批准号:
    11301329
  • 批准年份:
    2013
  • 资助金额:
    22.0 万元
  • 项目类别:
    青年科学基金项目
毫米波封装系统中高效、高精度的滤波器建模方法研究
  • 批准号:
    61101047
  • 批准年份:
    2011
  • 资助金额:
    25.0 万元
  • 项目类别:
    青年科学基金项目
超定偏微分方程组的几何研究与几何应用
  • 批准号:
    11171069
  • 批准年份:
    2011
  • 资助金额:
    40.0 万元
  • 项目类别:
    面上项目
动态环境下分布式自动服务组合的性能优化
  • 批准号:
    61070027
  • 批准年份:
    2010
  • 资助金额:
    32.0 万元
  • 项目类别:
    面上项目
典型团簇结构模式随尺度变化的理论计算研究
  • 批准号:
    21043001
  • 批准年份:
    2010
  • 资助金额:
    10.0 万元
  • 项目类别:
    专项基金项目
枢纽港选址及相关问题的算法设计
  • 批准号:
    71001062
  • 批准年份:
    2010
  • 资助金额:
    17.6 万元
  • 项目类别:
    青年科学基金项目
低纬度边缘海颗粒有机碳的卫星遥感算法研究
  • 批准号:
    41076114
  • 批准年份:
    2010
  • 资助金额:
    54.0 万元
  • 项目类别:
    面上项目
多跳无线 MESH 网络中 QoS 保障算法的研究设计和性能分析
  • 批准号:
    60902041
  • 批准年份:
    2009
  • 资助金额:
    20.0 万元
  • 项目类别:
    青年科学基金项目
多Agent系统联盟形成机制和算法的研究
  • 批准号:
    60573076
  • 批准年份:
    2005
  • 资助金额:
    23.0 万元
  • 项目类别:
    面上项目

相似海外基金

I-Corps: Cardiovascular Evaluation Algorithm
I-Corps:心血管评估算法
  • 批准号:
    2344006
  • 财政年份:
    2024
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Standard Grant
SWIFT-SAT: Unlimited Radio Interferometry: A Hardware-Algorithm Co-Design Approach to RAS-Satellite Coexistence
SWIFT-SAT:无限无线电干涉测量:RAS 卫星共存的硬件算法协同设计方法
  • 批准号:
    2332534
  • 财政年份:
    2024
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Standard Grant
A novel damage characterization technique based on adaptive deconvolution extraction algorithm of multivariate AE signals for accurate diagnosis of osteoarthritic knees
基于多变量 AE 信号自适应反卷积提取算法的新型损伤表征技术,用于准确诊断膝关节骨关节炎
  • 批准号:
    24K07389
  • 财政年份:
    2024
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Grant-in-Aid for Scientific Research (C)
REU Site: Algorithm Design --- Theory and Engineering
REU网站:算法设计---理论与工程
  • 批准号:
    2349179
  • 财政年份:
    2024
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Standard Grant
Development of a Novel EMG-Based Neural Interface for Control of Transradial Prostheses with Gripping Assistance
开发一种新型的基于肌电图的神经接口,用于通过抓取辅助控制经桡动脉假体
  • 批准号:
    10748341
  • 财政年份:
    2024
  • 资助金额:
    $ 1.41万
  • 项目类别:
Collaborative Research: Worm Algorithm and Diagrammatic Monte Carlo for Strongly Correlated Condensed Matter Systems
合作研究:强相关凝聚态系统的蠕虫算法和图解蒙特卡罗
  • 批准号:
    2335904
  • 财政年份:
    2024
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Continuing Grant
Collaborative Research: Worm Algorithm and Diagrammatic Monte Carlo for Strongly Correlated Condensed Matter Systems
合作研究:强相关凝聚态系统的蠕虫算法和图解蒙特卡罗
  • 批准号:
    2335905
  • 财政年份:
    2024
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Continuing Grant
SBIR Phase II: An Integrated Biomedical Platform and Custom Algorithm to Optimize Feeding Protocols for Preterm Infants
SBIR 第二阶段:用于优化早产儿喂养方案的综合生物医学平台和定制算法
  • 批准号:
    2335207
  • 财政年份:
    2024
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Cooperative Agreement
CAREER: Algorithm-Hardware Co-design of Efficient Large Graph Machine Learning for Electronic Design Automation
职业:用于电子设计自动化的高效大图机器学习的算法-硬件协同设计
  • 批准号:
    2340273
  • 财政年份:
    2024
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Continuing Grant
REU Site: Quantum Machine Learning Algorithm Design and Implementation
REU 站点:量子机器学习算法设计与实现
  • 批准号:
    2349567
  • 财政年份:
    2024
  • 资助金额:
    $ 1.41万
  • 项目类别:
    Standard Grant
{{ showInfoDetail.title }}

作者:{{ showInfoDetail.author }}

知道了