マトロイド交差問題と分割問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/08/07 04:53 UTC 版)
「マトロイド」の記事における「マトロイド交差問題と分割問題」の解説
マトロイド交差問題(Matroid Intersection Problem)は、2つのマトロイド(E,F1),(E,F2)が与えられたとき、|F|が最大となるようなF∈F1∩F2を求める問題である。マトロイド交差問題は多項式時間で解ける。また、3つ以上のマトロイド交差問題も同様に考えることができるが、これはNP困難問題である。 重み付き版についてもアルゴリズムが知られていて、2つの独立性オラクルの計算量の大きい方をαとするとO(|E|3α)で解ける。 マトロイド分割問題(Matroid Partitioning Problem)は k 個のマトロイド (E,F1),...,(E,Fk) が与えられたとき |X| が最大になるような分割可能な X⊆E を求める問題である。マトロイド交差問題とマトロイド分割問題は等価である。
※この「マトロイド交差問題と分割問題」の解説は、「マトロイド」の解説の一部です。
「マトロイド交差問題と分割問題」を含む「マトロイド」の記事については、「マトロイド」の概要を参照ください。
ウィキペディア小見出し辞書の「マトロイド交差問題と分割問題」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- マトロイド交差問題と分割問題のページへのリンク
