マトロイド・マッチングの構造理論とその回路網解析への応用

拟阵匹配的结构理论及其在网络分析中的应用

• 批准号: 08750083
• 负责人: 岩田 覚
• 金额: $ 0.51万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08750083/
• 关键词: マトロイド; 線型回路; アルゴリズム; 分解; 組合せ最適化; 劣モジュラ関数

線型マトロイド・マッチングは,ジャイレータ抵抗回路網の構造可解性判定に応用されている.しかし,実際問題としては,構造的に可解であることを保証するばかりでなく,数値誤差の影響を受けない組合せ的な情報に基づいて,数値計算の合理的な解法手順を示すことが望まれる.本研究では,線型マトロイド・マッチングの分解原理を確立し,分解を求める効率的な算法を与えることによって,この問題を解決した.さらに,海外との共同研究によって,線型マトロイド・マッチングの一般化である線型デルタマトロイド・パリティ問題に関する最大最小定理と効率的な多項式時間算法を導いた.その結果,線型マトロイド・マッチング問題が効率的に解ける仕組みについても理解が深まった.

线性矩阵匹配已应用于循环电阻网络的结构溶解度的测定。但是，作为一个实际问题，不仅需要确保其在结构上解决，而且还希望根据组合信息显示不受数值错误影响的数值计算的合理解决方案程序。在这项研究中，我们通过确定线性基质匹配的分解原理并提供了获得分解的有效方法来解决此问题。此外，与海外的联合研究得出了线性三角矩阵奇偶校验问题的最大最小定理和有效的多项式时间计算，这是线性矩阵匹配的概括。结果，我们加深了对如何有效解决线性矩阵匹配问题的理解。

项目成果

S.Itawata: "A Capacity Scaling Algorithm for Convex Cost Submodular Flows" Mathematical Programming. 76. 299-308 (1997)

S.Itawata：“凸成本子模流的容量缩放算法”数学规划。

S.Iwata & K.Murota: "Horizontal Principal Structure of Layerd Mixed Matrices:Deconpositon of Diserete Systems by Design-Variable Selections" SIAM Journal on Discrete Mathematics. 9. 71-86 (1996)

岩田南

S.Iwata,K.Murota,& I.Sakuta: "Primal-Dual Combinatorial Relaxation Algorithms for the Maximum Degree of Subdeterminants" SIAM Journal on Scientific Computing. 17. 993-1012 (1996)

S.岩田，K.室田，