2024-03-29T15:36:26Zhttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_oaipmhoai:ipsj.ixsq.nii.ac.jp:000317382024-03-29T05:26:34Z01164:02592:02607:02611
マトロイド被覆問題に対する発見的手法Heuristic algorithms for the matroid covering problemjpnhttp://id.nii.ac.jp/1001/00031738/Technical Reporthttps://ipsj.ixsq.nii.ac.jp/ej/?action=repository_action_common_download&item_id=31738&item_no=1&attribute_id=1&file_no=1Copyright (c) 2006 by the Information Processing Society of Japan群馬大学工学部情報工学科群馬大学工学部情報工学科群馬大学工学部情報工学科青木, 一正大舘陽太山崎, 浩一マトロイド被覆問題とは、グラフの樹相度を求める問題を一般化した問題である。マトロイド被覆問題は多項式時間で解けるものの、その時間計算量は決して低くない。近年、川野等は既に知られていたグラフの樹相度(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.AN1009593X情報処理学会研究報告アルゴリズム(AL)200649(2006-AL-106)17242006-05-182009-06-30