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

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

• 批准号: 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つあたり多項式時間といった効率良い列挙アルゴリズムが得られた．

今年，除了开发满足最大和最小值的子图枚举算法外，我们还构建了Size-K枚举算法。结果如下：（1）Size-K枚举算法在理论上被认为很难处理，我们计划开发一种启发式算法。但是，先前的研究成功地为枚举问题提出了合理的问题，并为其开发了有效的枚举算法。优化问题的困难是对大小约束枚举问题进行理论处理的困难。由于枚举问题是找到所有解决方案的问题，因此枚举问题显然比优化问题更加困难，而且由于优化问题的困难，枚举问题具有尺寸约束的困难。为了避免这种困难，这项研究介绍了对枚举问题的近似概念，例如优化算法，以及定义的枚举问题，具有近似约束，涉及具有大小约束的枚举问题。此外，在这项研究中，我们提出了一种近似枚举算法，该算法在每个溶液中以多项式时间运行，如果原始枚举问题很容易使用近似大小约束。 （2）我们已经开发了一种有效的枚举算法，该算法列举了稀疏子图，例如超小施罐树和具有内圆周约束的最大子图。在上一年，我们提供了一种算法来有效地从稀疏图中发现子图，但是今年，我们对算法进行了研究，该算法枚举了图形的次数，并研究了稀疏图的典型稀疏图，是稀疏图的典型稀疏图，以及具有内部周围构造的最大范围的属于局部包裹结构的列表。为了解决这些问题，获得了有效的枚举算法，例如微型施泰纳树的每条溶液的线性时间，以及针对最大内部外围约束的子图枚举的每个解决方案的多项式时间。

项目成果

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(イタリア)

比萨大学（意大利）

A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number

有界团数图中独立集的常量摊余时间枚举算法

• 发表时间: 2021
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Kazuhiro Kurita;Kunihiro Wasa;Takeaki Uno;Hiroki Arimura
• 通讯作者: Hiroki Arimura