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

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

• 批准号: 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/
• 关键词: マトロイド; 線型回路; アルゴリズム; 分解; 組合せ最適化; 劣モジュラ関数

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

The determination of structural solvability of linear resistance loop network In the case of practical problems, the construction of solvable problems is guaranteed, and numerical errors are affected by the combination of information. In this study, the decomposition principle of linear model is established, and the algorithm of decomposition to obtain the efficiency is solved. In this paper, overseas joint research, linear model, generalization, linear model, problem related to the maximum minimum theorem and efficiency polynomial time algorithm is introduced. As a result, the linear model of the problem is solved efficiently, and the problem is understood deeply.

项目成果

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.室田，