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

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

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

在这个财政年度，除了开发满足最大值和最大值的零件图枚举算法外，还构建了尺寸-K枚举算法。获得以下结果。但是，从到目前为止的研究中，它成功地提出了适当的问题，并有效地列举了列出尺寸限制的列举。很难用大小约束来处理枚举的原因是优化问题很困难。由于枚举问题是找到所有解决方案的问题，因此比优化问题显然很难枚举，因此由于优化问题的困难，很难遇到尺寸限制问题。为了避免这种困难，这项研究介绍了枚举近似的概念，例如优化算法，并定义了一个奖励问题，并对大小 - 构造的问题近似限制。此外，在这项研究中，如果原始的枚举问题很容易响应于近似尺寸限制的Ultra -small组组装问题，我们提出了一种近似值算法，该算法在每种溶液中以多项时间进行操作。 （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