マトロイド被覆問題に対する発見的手法

• Item type: SIG Technical Reports(1)
• 公開日: 2006-05-18
• タイトル: マトロイド被覆問題に対する発見的手法
• タイトル / 言語: en
• タイトル: Heuristic algorithms for the matroid covering problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 群馬大学工学部情報工学科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属: 群馬大学工学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science Gunma University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science Gunma University
• 著者所属(英): en
• 著者所属(英): Department of Computer Science Gunma University
• 著者名: 青木, 一正; 大舘陽太; 山崎, 浩一
• 著者名(英): Kazumasa, Aoki; Yota, Otachi; Koichi, Yamazaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: マトロイド被覆問題とは、グラフの樹相度を求める問題を一般化した問題である。マトロイド被覆問題は多項式時間で解けるものの、その時間計算量は決して低くない。近年、川野等は既に知られていたグラフの樹相度(edge arboricity)に対する線形時間で動作する2 倍近似アルゴリズムを、マトロイド被覆問題に対する発見的アルゴリズムに拡張した。本研究ではこの川野等が提案したアルゴリズムを、cographic マトロイドとstrict gammoid と呼ばれる2つのマトロイド上の被覆問題に対して実装し、実験的評価を行った。
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: The matroid covering problem can be considered as a generalization of edge arboricity problem. It is known that the matroid covering problem can be solved in polynomialtime, but the time complexity is still high. Kawano et al. have recently proposed a heuristic algorithm for the matroid covering problem by generalizing a linear time approximation algorithm with performance ratio 2 for edge arboricity problem. In this paper, we implement and evaluat the heuristic algorithm for cographic matroids and strict gammoids.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 情報処理学会研究報告アルゴリズム（AL）; 巻 2006, 号 49(2006-AL-106), p. 17-24, 発行日 2006-05-18
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会