Toward a radical extension of matroidal optimization theory

拟阵优化理论的根本扩展

• 批准号: 18K13451
• 负责人: 喜多 奈々緒
• 金额: $ 2.66万
• 依托单位: Tokyo University of Science
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Early-Career Scientists
• 财政年份: 2018
• 资助国家: 日本
• 起止时间: 2018-04-01 至 2023-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-18K13451/
• 关键词: 離散数学; 組合せ最適化; アルゴリズム; グラフ; ネットワーク; パリティ因子; 標準分解; グラフ理論; 離散最適化; マッチング理論; 離散数理

本年度には，前年度の成果をまとめる中で，パリティ因子に関して当初予定していなかった方向への発展を得た．パリティ因子（T-ジョイン）は，組合せ論の古典的なトピックであり，多項式可解クラスの中核に座すとされる最大マッチング問題の亜種に相当する．最小パリティ因子問題は，マッチングと類似の性質を持つ多項式時間可解である．その一方で，パリティ因子は，マッチングに比してずっと複雑な性質を呈し，また多くの未解決問題と関連するため，多項式可解性の本質を追究する上で特異かつ興味深い対象である．前年度には，マッチングに関する標準分解の一つである，二部グラフのDulmage-Mendelsohn (DM) 分解を，パリティ因子のための定理へと一般化したものを導出した．この成果については，本年度に単著論文として執筆し，オープンアクセスレポジトリにて公開した．しかし，パリティ因子の構造を把握するにはDM分解的な構造把握では不十分であることがその後の考察により明らかになったため，構成的特徴付けを与える標準分解の導出に取り組み，そのようなものとしてパリティ因子の二部的カテドラル分解を得た．カテドラル分解とは本来非二部グラフにおけるマッチングの構造を記述する標準分解である．しかし，二部グラフにおけるパリティ因子の構造を把握するにあたっては，カテドラル分解的な構造の二部的かつパリティ因子アナロジーによって十分な構造を記述する標準分解が与えられることが判った．さらにこの成果により，これまで不明であったDM分解とカテドラル分解の関係について一つの理解が得られた．この成果については単著論文として取りまとめオープンアクセスレポジトリに公開した．また，この成果に関連して得られた，耳分解などに関するさらに2本の論文を執筆中であり，近日中に公開する予定である．

今年，我们已经在汇编上一年的结果的方向上，从最初计划的方向上取得了发展。平价因子（T-Join）是组合理论的经典主题，对应于最大匹配问题的亚种，据说是多项式溶液类别的核心。最小奇偶因子问题是一种多项式时间解决方案，具有与匹配相似的属性。另一方面，奇偶校验因素比匹配表现出更为复杂的特性，并且与许多未解决的问题相关联，使它们成为追求多项式溶解性本质的单一有趣的对象。在上一年，我们将双方图（DM）分解（DM）分解（匹配的标准分解之一）的概括为平等因素定理。这项成就今年写为单人作者的论文，并在开放访问存储库中出版。但是，随后的考虑表明，DM依赖性的结构理解不足以理解奇偶元因素的结构，因此我们努力得出具有构成性特征的标准分解，因此，我们获得了奇偶校验因子的两部分大教堂分解。大教堂的分解最初是一种标准分解，描述了非双方图中匹配的结构。然而，发现在两分图中理解平价因子的结构时，可以通过两部分奇偶校验因子的类比来给出一种描述足够结构的标准分解。此外，该结果提供了对DM分解与大教堂分解之间以前未知的关系的理解。该结果被编译为单人作者的纸张，并在“开放访问存储库”中发布。此外，目前正在撰写另外两篇有关耳朵解剖和与此结果有关的信息，并将很快发表。

项目成果

Constructive Characterization of Critical Bidirected Graphs

关键双向图的建设性表征

• 发表时间: 2019
• 作者: Hidesato Kuroki;Kohei Soga;喜多 奈々緒;足立真訓;Sasaki Takiko;Masanori Adachi;Kohei Soga;喜多 奈々緒;Y. Kiriu and D.A. Mejia;喜多 奈々緒;Nanao Kita
• 通讯作者: Nanao Kita

非二部的 Dulmage-Mendelsohn 分解と Berge 双対の束構造

非二部 Dulmage-Mendelsohn 分解和 Berge 对偶丛结构

• 发表时间: 2018
• 作者: 村田 笑菜 ; 佐々木 多希子 ; 友枝 明保;喜多 奈々緒;M. Cardona and D.A. Mejia;Masanori Adachi;喜多 奈々緒
• 通讯作者: 喜多 奈々緒

Nonbipartite Dulmage-Mendelsohn Decomposition for Berge Duality

Berge 对偶性的非二部 Dulmage-Mendelsohn 分解

• DOI: 10.1007/978-3-319-94776-1_25
• 发表时间: 2018
• 期刊: ecture Notes in Computer Science
• 作者: Miguel Cardona;Lukas Klausner;Diego A. Mejia;足立真訓;Nanao Kita
• 通讯作者: Nanao Kita

二部グラフにおけるパリティ因子のためのカテドラル標準分解

二部图中奇偶校验因子的大教堂标准分解

• 发表时间: 2020
• 作者: Hidesato Kuroki;Kohei Soga;喜多 奈々緒;足立真訓;Sasaki Takiko;Masanori Adachi;Kohei Soga;喜多 奈々緒
• 通讯作者: 喜多 奈々緒

双向臨界グラフの構成的特徴づけ

双向临界图的建设性表征

• 发表时间: 2019
• 作者: Hidesato Kuroki;Kohei Soga;喜多 奈々緒;足立真訓;Sasaki Takiko;Masanori Adachi;Kohei Soga;喜多 奈々緒;Y. Kiriu and D.A. Mejia;喜多 奈々緒;Nanao Kita;喜多 奈々緒
• 通讯作者: 喜多 奈々緒