Development and Evaluations of Efficient Algorithms for Finding a Maximum Clique Based upon Nueral Networks
基于神经网络寻找最大团的高效算法的开发和评估
基本信息
- 批准号:02650261
- 负责人:
- 金额:$ 1.79万
- 依托单位:
- 依托单位国家:日本
- 项目类别:Grant-in-Aid for General Scientific Research (C)
- 财政年份:1990
- 资助国家:日本
- 起止时间:1990 至 1991
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
1. Given a graph of n nodes, we have devised an 0(n^3)-time algorithm NMCLIQ for finding a near-maximum clique. We have confirmed in experiments for several graphs with up to 400 nodes that the orders of maximal c)iques found by NMCLIQ are almost more than 85% of the maximum orders.2. We have developed an 0(n^3)-time algorithm RACLIQUE for finding a near-maximum clique in a given graph of n nodes. While the algorithm is based upon the notion of Boltzmann machines, it employs no simulated annealing and hence is simple to control its execution. We have confirmed in experiments for several random and nonrandom graphs with up to 400 nodes that almost optimum solutions can be found very efficiently. In addition, further improvements and variations are considered and verified to be very useful.3. We have devised two non-searching algorithms for the n-queen problem which are based upon the former resuit for finding a near-maximum clique. We have confirmed in experiments for up to 50, 000 queens that they are extremly efficient.
1.给定一个n个节点的图,我们设计了一个0(n^3)时间算法NMCLIQ来寻找一个近最大团。我们已经在实验中证实了几个多达400个节点的图,NMCLIQ发现的最大c)iques的阶数几乎超过最大阶数的85%。我们已经开发了一个0(n^3)-时间算法RACLIQUE寻找一个近最大团在一个给定的图的n个节点。虽然该算法是基于玻尔兹曼机的概念,但它不采用模拟退火,因此易于控制其执行。我们已经证实,在实验中的几个随机和非随机图与多达400个节点,几乎最优的解决方案可以非常有效地找到。此外,进一步的改进和变化被认为是非常有用的。我们设计了两个非搜索算法的n皇后问题的基础上,前resuit找到一个接近最大集团。我们已经在多达50000只蚁后的实验中证实,它们是非常有效的。
项目成果
期刊论文数量(30)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
YAMADA, Yoshiaki: ""Applying the notion of Boltzmann machines to have an algorithm for finding a near-maximum clique and its experimental evaluations"" IEICE Technical Report. COMP91. 63-68 (1991)
YAMADA、Yoshiaki:“应用玻尔兹曼机的概念来建立一种寻找接近最大团的算法及其实验评估””IEICE 技术报告。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
本村 陽一: "連続関数の領域区分近似を実現するネットワ-ク" 電子情報通信学会非線形問題研究会技術研究報告. NLPー91. 1-8 (1991)
本村阳一:“实现连续函数的域分割近似的网络”电子信息通信技术研究所非线性问题研究组的技术研究报告1-8(1991)。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
山田 義朗: "非探索アルゴリズムによるnーqueen問題の解法" 電子情報通信学会コンピュテ-ション研究会技術研究報告. COMPー90. 87-92 (1990)
Yoshiro Yamada:“使用非搜索算法解决 n 皇后问题”IEICE 计算研究组技术研究报告(1990 年)。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
山田 義明: "ボルツマンマシンの概念に基づいた近似最大クリ-ク抽出アルゴリズムとその実験的評価" 電子情報通信学会論文誌DーI.
Yoshiaki Yamada:“基于玻尔兹曼机概念的近似最大派系提取算法及其实验评估”IEICE Transactions DI。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
TAKAHASHI, Haruhisa: ""Biological plausibility of backpropagation"" IEICE Technical Report. NC90. 31-38 (1990)
TAKAHASHI、Haruhisa:“反向传播的生物学合理性”IEICE 技术报告。
- 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
图着色问题的加速构建算法
- DOI:
10.1587/transfun.2021dmp0011 - 发表时间:
2022 - 期刊:
- 影响因子:0
- 作者:
KANAHARA Kazuho;KATAYAMA Kengo;TOMITA Etsuji - 通讯作者:
TOMITA Etsuji
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.79万 - 项目类别:
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.79万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Improvement and extension of maximum-clique-finding algorithms with complexity analysis and their applications
复杂度分析最大团查找算法的改进和扩展及其应用
- 批准号:
19500010 - 财政年份:2007
- 资助金额:
$ 1.79万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Studies on Efficient Learning Algorithms from Examples
高效学习算法的实例研究
- 批准号:
13680435 - 财政年份:2001
- 资助金额:
$ 1.79万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Development and Applications of Efficient Algorithms for Combinatorial Optimization Problems
组合优化问题高效算法的开发与应用
- 批准号:
09680331 - 财政年份:1997
- 资助金额:
$ 1.79万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
Development and Evaluations of Efficient Algorithms for Combinatorial Optimization Problems
组合优化问题的高效算法的开发和评估
- 批准号:
06680311 - 财政年份:1994
- 资助金额:
$ 1.79万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)
相似国自然基金
基于Graph-PINN的层结稳定度参数化建模与沙尘跨介质耦合传输模拟研
- 批准号:
- 批准年份:2025
- 资助金额:0.0 万元
- 项目类别:省市级项目
平面三角剖分flip graph的强凸性研究
- 批准号:12301432
- 批准年份:2023
- 资助金额:30.00 万元
- 项目类别:青年科学基金项目
基于graph的多对比度磁共振图像重建方法
- 批准号:61901188
- 批准年份:2019
- 资助金额:24.5 万元
- 项目类别:青年科学基金项目
基于de bruijn graph梳理的宏基因组拼接算法开发
- 批准号:61771009
- 批准年份:2017
- 资助金额:50.0 万元
- 项目类别:面上项目
基于Graph和ISA的红外目标分割与识别方法研究
- 批准号:61101246
- 批准年份:2011
- 资助金额:22.0 万元
- 项目类别:青年科学基金项目
中国Web Graph的挖掘与应用研究
- 批准号:60473122
- 批准年份:2004
- 资助金额:23.0 万元
- 项目类别:面上项目
相似海外基金
Conference: 9th Lake Michigan Workshop on Combinatorics and Graph Theory
会议:第九届密歇根湖组合学和图论研讨会
- 批准号:
2349004 - 财政年份:2024
- 资助金额:
$ 1.79万 - 项目类别:
Standard Grant
Collaborative Research: OAC Core: Distributed Graph Learning Cyberinfrastructure for Large-scale Spatiotemporal Prediction
合作研究:OAC Core:用于大规模时空预测的分布式图学习网络基础设施
- 批准号:
2403312 - 财政年份:2024
- 资助金额:
$ 1.79万 - 项目类别:
Standard Grant
Next-Generation Distributed Graph Engine for Big Graphs
适用于大图的下一代分布式图引擎
- 批准号:
DP240101322 - 财政年份:2024
- 资助金额:
$ 1.79万 - 项目类别:
Discovery Projects
Large Graph Limits of Stochastic Processes on Random Graphs
随机图上随机过程的大图极限
- 批准号:
EP/Y027795/1 - 财政年份:2024
- 资助金额:
$ 1.79万 - 项目类别:
Research Grant
Computing over Compressed Graph-Structured Data
压缩图结构数据的计算
- 批准号:
EP/X039447/1 - 财政年份:2024
- 资助金额:
$ 1.79万 - 项目类别:
Research Grant
CAREER: Strategic Interactions, Learning, and Dynamics in Large-Scale Multi-Agent Systems: Achieving Tractability via Graph Limits
职业:大规模多智能体系统中的战略交互、学习和动态:通过图限制实现可处理性
- 批准号:
2340289 - 财政年份:2024
- 资助金额:
$ 1.79万 - 项目类别:
Continuing Grant
Toward Trustworthy Generative AI by Integrating Large Language Model with Knowledge Graph
通过将大型语言模型与知识图相结合,迈向可信赖的生成式人工智能
- 批准号:
24K20834 - 财政年份:2024
- 资助金额:
$ 1.79万 - 项目类别:
Grant-in-Aid for Early-Career Scientists
CAREER: Fast Scalable Graph Algorithms
职业:快速可扩展图算法
- 批准号:
2340048 - 财政年份:2024
- 资助金额:
$ 1.79万 - 项目类别:
Continuing Grant
Collaborative Research: AF: Small: Structural Graph Algorithms via General Frameworks
合作研究:AF:小型:通过通用框架的结构图算法
- 批准号:
2347322 - 财政年份:2024
- 资助金额:
$ 1.79万 - 项目类别:
Standard Grant
REU Site: Graph Learning and Network Analysis: from Foundations to Applications (GraLNA)
REU 网站:图学习和网络分析:从基础到应用 (GraLNA)
- 批准号:
2349369 - 财政年份:2024
- 资助金额:
$ 1.79万 - 项目类别:
Standard Grant