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

• Item type: SIG Technical Reports(1)
• 公開日: 1996-03-15
• タイトル: 重みつきマトロイドのK番目に重い基を求める
• タイトル / 言語: en
• タイトル: K Best Bases of a Weighted Matroid
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学工学系研究科計数工学
• 著者所属: 東京都立大学理学部数学教室
• 著者所属(英): en
• 著者所属(英): Department of Mathematical Engineering and Information Physics, Faculty of Engineering, University of Tokyo
• 著者所属(英): en
• 著者所属(英): Department of Mathematics, Faculty of Science, Tokyo Metropolitan University
• 著者名: 松井, 知己; 松井, 泰子
• 著者名(英): Tomoki, Matsui; Yasuko, Matsui
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿では、マトロイドの基を生成する算法をいくつか提案する。提案する基をすべて列挙する算法は、時間計算量がO（β(+r^)）記憶容量はO(^)である。ただし、βは基の個数、rはマトロイドのランク、O(+)はサーキットオラクルの計算量である。重みつきマトロイドに対しては、基を重みの重い順に列挙する算法の提案を行なう。この算法でK番目に重い基を求めるのに必要な時間計算量はO(^2+K(+r^2+log )）であり、必要記憶容量はO(r)である。ただしnは台集合の大きさである。また重みが全て整数のときは、基数ヒープを用いることにより、時間計算量はO((+r^2+log )）となり空間計算量はO(og W+Kr)となる。ただしWは重みの絶対値の最大の値である。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: In this paper, we propose an algorithm which generates the bases of matroids. The enumeration algorithm requires O(β(T+r^2)) time and O(r^3) space where β is the number of bases, r is the rank of a given matroid and O(T+r) is the time complexity of circuit oracle. In the last section, we describe a ranking algorithm which generates all the bases in order of nonincreasing order of weight. The algorithm requires O(n^2+K(T+r^2+log n)) time and O(Krn) space for finding K best bases. When the weight vector is integer valued, time complexity becomes O(K(T+r^2+log W)) time and the space complexity becomes O(log W+Krn) space by employing the radix heap structure where W is the maximum absolute value of weights.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 1996, 号 28(1995-AL-050), p. 33-40, 発行日 1996-03-15
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会