効率的な最大および極大クリーク抽出アルゴリズムの開発と応用
高效最大派系提取算法的开发与应用
基本信息
- 批准号:17K00006
- 负责人:
- 金额:$ 2.91万
- 依托单位:
- 依托单位国家:日本
- 项目类别:Grant-in-Aid for Scientific Research (C)
- 财政年份:2017
- 资助国家:日本
- 起止时间:2017 至 2021
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
最大クリーク抽出は多くの実応用問題解決に対して有用であるがNP困難問題であり,一般的には求解に非常に長時間を要する.最大クリーク厳密解抽出の分枝限定アルゴリズムに対するこれまでの研究により,最大クリークの近似解が非常に有効に活用出来ることを明らかにしてきた.その近似精度が良くなれば分枝限定はより有効に働く.しかし,近似解抽出のために時間を要すると,総実行時間としては必ずしも短縮とはならず,近似精度と時間との兼ね合いが重要となる.そこで先ず,最大クリーク近似解の抽出を一層高速化し,その上で精度を向上させることにより,総合的に最大クリーク厳密解抽出を効率化した.続いて,分枝限定のために近似彩色だけでなくMaxSATも用いることにより分枝限定がより強力化されることをこれまでに確認してきたが,MaxSATあるいはその簡略形実行のためのオーバーヘッドの大きさが最大クリーク厳密解抽出総実行時間短縮の妨げとなっていた.これに対しては,MaxSATの簡略形と従来提唱してきていた再番号付け(再彩色)との類似性に着目して両者を融合させることにより,これまでよりも少ないオーバーヘッドによって,有効な分枝限定効果を発揮出来るようにした.さらに,分枝限定アルゴリズムの内部動作は入力グラフの特徴に応じて効率が左右されるため,出来る限り効率がより発揮されるようにと内部動作を適応的に切り替えるようにした.以上を総合することにより,最大クリーク厳密解抽出のための従来の分枝限定アルゴリズムを有意に高速化することに成功した.このような最大クリーク厳密解抽出アルゴリズムは,容易に最大クリーク全列挙アルゴリズムへと拡張出来る.これにより,符号理論における最良な多元単一削除訂正符号の構成に関しての新たな知見を得ることが出来た.また,極大クリーク全列挙問題についても理論的,実験的に検討を行い,有効な進展結果を得た.
Maximal extraction of multiple-use problem solving is useful for NP-hard problems, and general problem solving is time-consuming. The branch restriction of maximum solution extraction is studied. The approximate solution of maximum solution extraction is used in the study. Approximation accuracy is good, branching is limited, and approximation accuracy is good. Approximate solution extraction time is important, travel time is important, approximate accuracy is important, and time is important. In the first place, the extraction of the maximum approximation solution is a layer of high speed, the upper accuracy is an upward step, and the maximum approximation solution extraction of the total solution is an efficiency. In the middle of the branch limit, the approximate color is divided into two parts: MaxSAT, MaxSAT and MaxSAT. In this case, MaxSAT's simplified form is used to refer to the second color, and the similarity is used to refer to the fusion of the first color. In addition, the internal action of the branch limit is to enter the force of the characteristics of the branch limit. The internal action of the branch limit is to enter the force of the characteristics of the branch limit. The above is a combination of the following: The maximum number of entries in the list is easy to find. The theory of symbols is the best way to eliminate and correct the composition of symbols. The maximum number of problems in the whole series is calculated theoretically, and the actual results are obtained.
项目成果
期刊论文数量(0)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
最大クリーク問題に対する探索頻度情報にもとづく反復k-opt局所探索法の性能
基于搜索频率信息的迭代k-opt局部搜索方法求解最大团问题的性能
- DOI:
- 发表时间:2019
- 期刊:
- 影响因子:0
- 作者:金原一歩;片山謙吾;富田悦次;松崎空良
- 通讯作者:松崎空良
Speeding-Up of Construction Algorithms for the Graph Coloring Problem
图着色问题的构造算法加速
- DOI:
- 发表时间:2020
- 期刊:
- 影响因子:0
- 作者:Kazuho Kanahara;Kengo Katayama;Takafumi Miyake;Etsuji Tomita
- 通讯作者:Etsuji Tomita
Enumeration of maximum cliques and its application to coding theory
最大团的枚举及其在编码理论中的应用
- DOI:
- 发表时间:2019
- 期刊:
- 影响因子:0
- 作者:金原一歩;片山謙吾;富田悦次;松崎空良;Etsuji Tomita
- 通讯作者:Etsuji Tomita
Efficient algorithms for finding maximum and maximal cliques
寻找最大和最大派系的有效算法
- DOI:
- 发表时间:2017
- 期刊:
- 影响因子:0
- 作者:長尾篤樹;松崎空良;富田悦次;伊藤大雄;若月光夫;西野哲朗;光武 朗,野崎隆之,富田悦次;Etsuji Tomita
- 通讯作者:Etsuji Tomita
{{
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 }}
富田 悦次其他文献
NP完全問題の計算量評価・改善について-最大クリーク問題を中心として-
关于NP完全问题的计算复杂度评估和改进 - 关注最大派系问题 -
- DOI:
- 发表时间:
2008 - 期刊:
- 影响因子:0
- 作者:
中西裕陽;富田悦次;中西 裕陽;富田 悦次 - 通讯作者:
富田 悦次
Polynomiasl time identification of strict deterministic restricted one-counter automata in some class from positive data
正数据中某类严格确定性限制单计数器自动机的多项式时间辨识
- DOI:
- 发表时间:
2008 - 期刊:
- 影响因子:0
- 作者:
K. Iwama;H. Morizumi;J. Tarui;中西 裕陽;Mitsuo Wakatsuki;清野 和司;富田 悦次;Mitsuo Wakatsuki - 通讯作者:
Mitsuo Wakatsuki
オートマトン・言語理論(第19刷・改訂増刷)
自动机与语言理论(第19版/修订重印)
- DOI:
- 发表时间:
2008 - 期刊:
- 影响因子:0
- 作者:
高橋治久;堀田一弘;富田悦次;広中平祐;富田 悦次;富田 悦次 - 通讯作者:
富田 悦次
質問と判例による単純決定性言語の多項式時間学習を可能とさせる十分条件
使用问题和先例进行简单确定性语言多项式时间学习的充分条件
- DOI:
- 发表时间:
2005 - 期刊:
- 影响因子:0
- 作者:
但馬 康宏;小谷 善行;富田 悦次 - 通讯作者:
富田 悦次
オートマトン・言語理論(第20刷・改訂増刷)
自动机/语言理论(第20次印刷/修订重印)
- DOI:
- 发表时间:
2009 - 期刊:
- 影响因子:0
- 作者:
高橋治久;堀田一弘;富田悦次;広中平祐;富田 悦次 - 通讯作者:
富田 悦次
富田 悦次的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('富田 悦次', 18)}}的其他基金
効率的な極大クリーク抽出アルゴリズムの開発と計算量評価に関する研究
高效最大派系提取算法开发及计算复杂度评估研究
- 批准号:
60550259 - 财政年份:1985
- 资助金额:
$ 2.91万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)
オートマトン・形式文法の等価性判定アルゴリズムの開発と計算量解析に関する研究
自动机和形式语法的等价判定算法和计算复杂度分析的开发研究
- 批准号:
58550240 - 财政年份:1983
- 资助金额:
$ 2.91万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)
オートマトン・形式文法系の効率的等価性判定法とその応用に関する研究
自动机和形式语法系统的高效等价判定方法及其应用研究
- 批准号:
57550214 - 财政年份:1982
- 资助金额:
$ 2.91万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)
離散的システムの等価性判定アルゴリズムと図式的動作表現法の研究
离散系统等价判定算法及图解行为表示方法研究
- 批准号:
X00095----565123 - 财政年份:1980
- 资助金额:
$ 2.91万 - 项目类别:
Grant-in-Aid for General Scientific Research (D)
相似海外基金
効率的な極大クリーク抽出アルゴリズムの開発と計算量評価に関する研究
高效最大派系提取算法开发及计算复杂度评估研究
- 批准号:
60550259 - 财政年份:1985
- 资助金额:
$ 2.91万 - 项目类别:
Grant-in-Aid for General Scientific Research (C)