疎なグラフに対する効率良い部分構造列挙アルゴリズムの研究

稀疏图高效子结构枚举算法研究

• 批准号: 19J10761
• 负责人: 栗田 和宏
• 金额: $ 1.09万
• 依托单位: National Institute of Informatics (2020)Hokkaido University (2019)
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2019
• 资助国家: 日本
• 起止时间: 2019-04-25 至 2021-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-19J10761/
• 关键词: 部分構造列挙; ならし多項式時間; 疎性; 最大クリークサイズ

本年度は極大性，極小性を満たす部分グラフ列挙アルゴリズムの開発に加え，サイズ-k列挙アルゴリズムの構築を行なった．その成果として，以下の結果が得られた.（1) サイズ-k列挙アルゴリズムは，理論的に扱うことは困難であると考え，ヒューリスティックアルゴリズムの開発を予定していた．しかし，これまでの研究から，サイズ制約付きの列挙問題に対し，妥当な問題の定式化とそれに対する効率良い列挙アルゴリズムの開発に成功した．サイズ制約付き列挙問題を理論的に扱うことが困難な理由として，最適化問題の困難性がある．列挙問題が全ての解を見つける問題であることから，明らかに最適化問題より列挙問題の方が困難であるため，最適化問題の困難性から，サイズ制約付き列挙問題が困難である．この困難性を避けるため，本研究では最適化アルゴリズムのように，列挙問題に近似という概念を導入し，サイズ制約付き列挙問題に対し，近似制約付きの列挙問題を定義した．さらに本研究では近似的なサイズ制約付きの極小部分集合列挙問題に対し，元の列挙問題が容易であるならば，解1つあたり多項式時間で動作する近似列挙アルゴリズムを提案した．（2）極小シュタイナー木や内周制約付き極大部分グラフといった疎な部分グラフを列挙する効率良い列挙アルゴリズムの開発を行った．前年度は疎なグラフから部分グラフを効率良くに発見するアルゴリズムを与えたが，本年度はグラフ中から疎な部分グラフを列挙するアルゴリズムについて研究を行い，疎なグラフの中でも代表的な疎なグラフである木構造と，局所的に木構造を持つ内周制約付き極大部分グラフ列挙について研究を行なった．これらの問題に対し，極小シュタイナー木については解1つあたり線形時間，極大内周制約付き部分グラフ列挙については1つあたり多項式時間といった効率良い列挙アルゴリズムが得られた．

This year, the maximum and minimum properties of the product are increased by the development of the product, and the product is constructed. The following results were obtained. (1) The development of the theory is determined by the difficulty of the theory. The research on this topic is based on the successful development of the problem formulation and problem optimization. The difficulty of the optimization problem. The problem of optimization is difficult. The problem of optimization is difficult. The problem of optimization is difficult. In this paper, we introduce the concept of approximate constraint problem into optimization problem, and define approximate constraint problem. In this paper, we propose a new method for solving approximate column problems in polynomial time. (2) The minimum length of the inner circumference of the tree is limited to the maximum length of the inner circumference of the tree. In the previous year, the rate of partial improvement was very good, but in the current year, the research was carried out in the middle of partial improvement, and the wood structure represented by the middle of partial improvement was carried out in the middle of partial improvement. This problem is solved in a minimal way, in a linear way, in a maximal way, in a polynomial way, in a minimal way, in a polynomial way, in a maximal way, in a linear way, in a maximal way.

项目成果

Polynomial delay enumeration for Steiner problems

Steiner 问题的多项式延迟枚举

• 发表时间: 2020
• 作者: Yasuaki Kobayashi;Kazuhiro Kurita;Kunihiro Wasa
• 通讯作者: Kunihiro Wasa

グラフの極小多分割カットの効率よい列挙

图的最小多分区割的高效枚举

• 发表时间: 2020
• 作者: Kurita Kazuhiro;Wasa Kunihiro;Uno Takeaki;Arimura Hiroki;Kazuhiro Kurita;Kazuhiro Kurita;彭毛 才旦;Kazuhiro Kurita;彭毛 才旦;栗田 和宏;栗田 和宏;彭毛才旦;栗田 和宏
• 通讯作者: 栗田 和宏

Finding the Anticover of a String

寻找字符串的反覆盖

• 发表时间: 2020
• 作者: Mai Alzamel;Alessio Conte;Shuhei Denzumi;Roberto Grossi;Costas S. Iliopoulos;Kazuhiro Kurita and Kunihiro Wasa
• 通讯作者: Kazuhiro Kurita and Kunihiro Wasa

University of Pisa(イタリア)

比萨大学（意大利）

頂点数定数の禁止部分グラフを持つグラフに 対する独立点集合のならし定数時間列挙

具有恒定顶点数的禁止子图的独立点集的正则化常数时间枚举

• 发表时间: 2019
• 作者: Kurita Kazuhiro;Wasa Kunihiro;Uno Takeaki;Arimura Hiroki;Kazuhiro Kurita;Kazuhiro Kurita;彭毛 才旦;Kazuhiro Kurita;彭毛 才旦;栗田 和宏;栗田 和宏;彭毛才旦;栗田 和宏;彭毛才旦;Kazuhiro Kurita;彭毛 才旦;栗田 和宏;彭毛 才旦;Kazuhiro Kurita;彭毛 才旦;栗田 和宏;Kazuhiro Kurita;彭毛 才旦;栗田 和宏
• 通讯作者: 栗田 和宏