マトロイド・マッチングの構造理論とその回路網解析への応用
【研究分野】工学基礎
【研究キーワード】
マトロイド / 線型回路 / アルゴリズム / 分解 / 組合せ最適化 / 劣モジュラ関数
【研究成果の概要】
線型マトロイド・マッチングは,ジャイレータ抵抗回路網の構造可解性判定に応用されている.しかし,実際問題としては,構造的に可解であることを保証するばかりでなく,数値誤差の影響を受けない組合せ的な情報に基づいて,数値計算の合理的な解法手順を示すことが望まれる.
本研究では,線型マトロイド・マッチングの分解原理を確立し,分解を求める効率的な算法を与えることによって,この問題を解決した.
さらに,海外との共同研究によって,線型マトロイド・マッチングの一般化である線型デルタマトロイド・パリティ問題に関する最大最小定理と効率的な多項式時間算法を導いた.その結果,線型マトロイド・マッチング問題が効率的に解ける仕組みについても理解が深まった.
【研究代表者】
【研究種目】奨励研究(A)
【研究期間】1996
【配分額】800千円 (直接経費: 800千円)