@techreport{oai:ipsj.ixsq.nii.ac.jp:00031738,
 author = {青木, 一正 and 大舘陽太 and 山崎, 浩一 and Kazumasa, Aoki and Yota, Otachi and Koichi, Yamazaki},
 issue = {49(2006-AL-106)},
 month = {May},
 note = {マトロイド被覆問題とは、グラフの樹相度を求める問題を一般化した問題である。マトロイド被覆問題は多項式時間で解けるものの、その時間計算量は決して低くない。近年、川野等は既に知られていたグラフの樹相度(edge arboricity)に対する線形時間で動作する2 倍近似アルゴリズムを、マトロイド被覆問題に対する発見的アルゴリズムに拡張した。本研究ではこの川野等が提案したアルゴリズムを、cographic マトロイドとstrict gammoid と呼ばれる2つのマトロイド上の被覆問題に対して実装し、実験的評価を行った。, 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.},
 title = {マトロイド被覆問題に対する発見的手法},
 year = {2006}
}