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

点击翻译按钮获取中文摘要

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に採択された．