ポリ・リンキングシステムの分解と一般化ポリマトロイドのマイナーについて

スポンサーリンク

概要

• 論文の詳細を見る

• 著者が提示した劣モジュラー関数の分解の一般的手法がSchrijverの定義したポリ・リンキングシステムに適用できることを示し、ポリマトロイド共通ベクトル問題に対した場合と相似の結果が導出できることを示す。この過程でポリ・リンキングシステムに我々の分解原理を適用して得られる部分システムは、もはやポリ・リンキングシステムではないことが明らかになる。これはポリ・リンキングシステムをFrankの定義した一般化ポリマトロイド(generalized polymatroid)の特別な場合とみなし、ここで新たに一般化ポリマトロイドのマイナーの概念を導入することによって、もとのポリ・リンキングシステムを一般化ポリマトロイドとみなせば、分解で得られた部分システムがそのマイナーになり理論的に整合的に説明される。二部グラフのいわゆるDulmage-Mendelsohn分解は重みづけのパラメータを導入した場合も含めて、本論文で定義した分解のひとつの特別な場合になっている。

• 社団法人日本オペレーションズ・リサーチ学会の論文

著者

• 中村 政隆

  東京大学

関連論文

• 2-E-9 2次元アフィン凸幾何のmax-flow min-cut定理(離散最適化)
• 閉集合族のサーキット、コサーキットのパッキング(組合せ(1))
• 有向グラフ点探索アンチマトロイドの禁止マイナーによる特徴付け(グラフ・ネットワーク(1))
• An Intersection Theorem for Disjoint-Cut Systems
• 理想グラフに於ける強い予想について(グラフ・ネットワーク(2))
• Edmonds-Giles による Totally Dual Integral なシステムの擬劣モジュラー関数上への拡張(組合せ・グラフ・ネットワーク)
• ポリ・リンキングシステムの分解と一般化ポリマトロイドのマイナーについて
• 2-I-5 The rooted circuits of closure systems and the full implicational systems

スポンサーリンク