マッチング問題の代数的拡張に対する組合せ的アプローチ

匹配问题代数扩展的组合方法

• 批准号: 20K23323
• 负责人: 岩政 勇仁
• 金额: $ 1.83万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Research Activity Start-up
• 财政年份: 2020
• 资助国家: 日本
• 起止时间: 2020-09-11 至 2024-03-31
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-20K23323/
• 关键词: Edmonds問題; 重み付きEdmonds問題; 非可換Edmonds問題; 重み付き非可換Edmonds問題; 線形マトロイド交叉; 最大最小定理; マトロイド; 組合せ最適化; 代数的最適化; マッチング理論; アルゴリズム

2×2型分割多項式行列の小行列式最大次数列を求める組合せ的強多項式時間アルゴリズムを提案した論文"A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with 2×2 submatrices"が，Mathematical Programming, Series Aに採択された．また，この成果をThe 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2023)で発表し，多数の有用なフィードバックを得た．また，Edmonds問題の特殊クラスである線形マトロイド交叉に対して，「遷移可能性」という観点から研究を行った．それにより，有向木（グラフ的マトロイドと分割マトロイドの交叉）の遷移可能性判定問題が多項式時間で解けることが判明した．この成果をまとめた論文"Reconfiguring (non-spanning) arborescences"が論文誌Theoretical Computer Scienceに採択された．

A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with 2 × 2 submatrices is proposed in this paper. The 12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2023) was launched. Edmonds problem special category: linear category: cross category: possibility of migration category: research category: The problem of determining the migration probability of a directional tree is solved in polynomial time. The paper "Reconfiguring (non-spanning) arborescences" was published in Theoretical Computer Science.

项目成果

Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications

具有交集约束的最优拟阵基：评估拟阵、M-凸函数及其应用

• DOI: 10.1007/s10107-021-01625-2
• 发表时间: 2021
• 期刊: Mathematical Programming
• 影响因子: 2.7
• 作者: Yuni Iwamasa;Kenjiro Takazawa
• 通讯作者: Kenjiro Takazawa

Reconfiguring (non-spanning) arborescences

重新配置（非跨越）树状结构

• DOI: 10.1016/j.tcs.2022.12.007
• 发表时间: 2023
• 期刊: Theoretical Computer Science
• 影响因子: 1.1
• 作者: Takehiro Ito;Yuni Iwamasa;Yasuaki Kobayashi;Yu Nakahata;Yota Otachi;Kunihiro Wasa
• 通讯作者: Kunihiro Wasa

Monotone edge flips to an orientation of maximum edge-connectivity a la Nash-Williams

单调边缘翻转到最大边缘连通性的方向，如纳什-威廉姆斯

• DOI: 10.1145/3561302
• 发表时间: 2023
• 期刊: ACM Transactions on Algorithms
• 影响因子: 1.3
• 作者: Takehiro Ito;Yuni Iwamasa;Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;Shun-ichi Maezawa;Yuta Nozaki;Yoshio Okamoto;Kenta Ozeki
• 通讯作者: Kenta Ozeki

Reconstructing phylogenetic trees from multipartite quartet systems

从多部分四重系统重建系统发育树

• DOI: 10.1007/s00453-022-00945-9
• 发表时间: 2022
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: Yuho Tanaka;Kazunori Uruma;Tomoki Nakao;Yuni Iwamasa;田中 勇帆，雨車 和憲，中尾 朋喜;Hirai Hiroshi and Iwamasa Yuni
• 通讯作者: Hirai Hiroshi and Iwamasa Yuni

2部マッチング理論の代数的一般化について

关于二分匹配理论的代数推广

• 发表时间: 2021
• 作者: Yuni Iwamasa;Kenjiro Takazawa;Yuni Iwamasa;Yuni Iwamasa;岩政 勇仁;岩政 勇仁;Yuni Iwamasa;岩政 勇仁
• 通讯作者: 岩政 勇仁