{"links":{},"id":31738,"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00031738","sets":["1164:2592:2607:2611"]},"path":["2611"],"owner":"1","recid":"31738","title":["マトロイド被覆問題に対する発見的手法"],"pubdate":{"attribute_name":"公開日","attribute_value":"2006-05-18"},"_buckets":{"deposit":"7e9e6ff8-8c0a-4529-97de-5fc11f166823"},"_deposit":{"id":"31738","pid":{"type":"depid","value":"31738","revision_id":0},"owners":[1],"status":"published","created_by":1},"item_title":"マトロイド被覆問題に対する発見的手法","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"マトロイド被覆問題に対する発見的手法"},{"subitem_title":"Heuristic algorithms for the matroid covering problem","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2006-05-18","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"群馬大学工学部情報工学科"},{"subitem_text_value":"群馬大学工学部情報工学科"},{"subitem_text_value":"群馬大学工学部情報工学科"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Department of Computer Science Gunma University","subitem_text_language":"en"},{"subitem_text_value":"Department of Computer Science Gunma University","subitem_text_language":"en"},{"subitem_text_value":"Department of Computer Science Gunma University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/31738/files/IPSJ-AL06106003.pdf"},"date":[{"dateType":"Available","dateValue":"2008-05-18"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL06106003.pdf","filesize":[{"value":"114.9 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"0e43c7e2-6d95-4a2c-9619-d9e41e6a2218","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2006 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"青木, 一正"},{"creatorName":"大舘陽太"},{"creatorName":"山崎, 浩一"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kazumasa, Aoki","creatorNameLang":"en"},{"creatorName":"Yota, Otachi","creatorNameLang":"en"},{"creatorName":"Koichi, Yamazaki","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"マトロイド被覆問題とは、グラフの樹相度を求める問題を一般化した問題である。マトロイド被覆問題は多項式時間で解けるものの、その時間計算量は決して低くない。近年、川野等は既に知られていたグラフの樹相度(edge arboricity)に対する線形時間で動作する2 倍近似アルゴリズムを、マトロイド被覆問題に対する発見的アルゴリズムに拡張した。本研究ではこの川野等が提案したアルゴリズムを、cographic マトロイドとstrict gammoid と呼ばれる2つのマトロイド上の被覆問題に対して実装し、実験的評価を行った。","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"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.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"24","bibliographic_titles":[{"bibliographic_title":"情報処理学会研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"17","bibliographicIssueDates":{"bibliographicIssueDate":"2006-05-18","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"49(2006-AL-106)","bibliographicVolumeNumber":"2006"}]},"relation_version_is_last":true,"weko_creator_id":"1"},"created":"2025-01-18T23:01:00.112170+00:00","updated":"2025-01-22T16:30:27.171942+00:00"}