重みつきマトロイドのK番目に重い基を求める

スポンサーリンク

概要

論文の詳細を見る
本稿では、マトロイドの基を生成する算法をいくつか提案する。提案する基をすべて列挙する算法は、時間計算量が O(β(T+r^2)) 記憶容量は O(r^3)である。ただし、βは基の個数、r はマトロイドのランク、O(T+r)はサーキットオラクルの計算量である。重みつきマトロイドに対しては、基を重みの重い順に列挙する算法の提案を行なう。この算法でK番目に重い基を求めるのに必要な時間計算量は O(n^2+K(T+r^2+logn))であり、必要記憶容量は O(Krn)である。ただし n は台集合の大きさである。また重みが全て整数のときは、基数ヒープを用いることにより、時間計算量は O(K(T+r^2+logW))となり空間計算量は O(logW+Krn)となる。ただし W は重みの絶対値の最大の値である。
一般社団法人情報処理学会の論文
1996-03-15

著者

関連論文

もっと見る

スポンサーリンク