{"created":"2023-05-15T15:31:04.567884+00:00","id":3641,"links":{},"metadata":{"_buckets":{"deposit":"a80411cb-13cd-4eeb-be10-35b1bc01b8af"},"_deposit":{"created_by":3,"id":"3641","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"3641"},"status":"published"},"_oai":{"id":"oai:barrel.repo.nii.ac.jp:00003641","sets":["1:15"]},"author_link":["7734","7735"],"item_8_biblio_info_4":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2007-12","bibliographicIssueDateType":"Issued"},"bibliographicPageEnd":"4","bibliographicPageStart":"1","bibliographicVolumeNumber":"112","bibliographic_titles":[{"bibliographic_title":"Discussion paper series"}]}]},"item_8_description_20":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"頂点被覆は, NP 困難な組合せ最適化問題ゆえに, 多項式時間では解き得ないと考えられている. \n他方, 頂点被覆にはいくつかの近似解法が提案されている. これら近似解法には, 大きく分けて二種類, 即ち, 与えられたグラフの最大次数をΔ として近似率O(log Δ) を与えるものと近似率2 を与えるものがある. 近年, この頂点被覆に対するある近似解法が, 近似率√Δ/2+3/2を与えることが示された. ここでは, その近似率を導出した解析に若干の修正を加えて, より良い近似率を導くことを試みる.","subitem_description_type":"Abstract"}]},"item_8_full_name_3":{"attribute_name":"著者別名","attribute_value_mlt":[{"nameIdentifiers":[{"nameIdentifier":"7735","nameIdentifierScheme":"WEKO"}],"names":[{"name":"Iida, Hiroshi"}]}]},"item_8_publisher_5":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"小樽商科大学ビジネス創造センター"}]},"item_8_subject_18":{"attribute_name":"日本十進分類法","attribute_value_mlt":[{"subitem_subject":"410","subitem_subject_scheme":"NDC"}]},"item_8_subject_19":{"attribute_name":"NIIサブジェクト","attribute_value_mlt":[{"subitem_subject":"数学","subitem_subject_scheme":"Other"}]},"item_8_version_type_17":{"attribute_name":"テキストバージョン","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"飯田, 浩志"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2016-01-26"}],"displaytype":"detail","filename":"no112.pdf","filesize":[{"value":"186.2 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"no112.pdf","url":"https://barrel.repo.nii.ac.jp/record/3641/files/no112.pdf"},"version_id":"1ec99f28-0803-4059-b13a-12ad100a5a10"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"組合せ最適化","subitem_subject_scheme":"Other"},{"subitem_subject":"集合被覆","subitem_subject_scheme":"Other"},{"subitem_subject":"頂点被覆","subitem_subject_scheme":"Other"},{"subitem_subject":"近似アルゴリズム","subitem_subject_scheme":"Other"},{"subitem_subject":"近似率","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"technical report","resourceuri":"http://purl.org/coar/resource_type/c_18gh"}]},"item_title":"頂点被覆へのリスト減少法の解析に関する一考察","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"頂点被覆へのリスト減少法の解析に関する一考察"}]},"item_type_id":"8","owner":"3","path":["15","145"],"pubdate":{"attribute_name":"公開日","attribute_value":"2008-06-17"},"publish_date":"2008-06-17","publish_status":"0","recid":"3641","relation_version_is_last":true,"title":["頂点被覆へのリスト減少法の解析に関する一考察"],"weko_creator_id":"3","weko_shared_id":-1},"updated":"2023-07-20T08:28:40.025208+00:00"}