{"created":"2023-05-15T11:59:41.017940+00:00","id":6230,"links":{},"metadata":{"_buckets":{"deposit":"eb14e678-f7f0-4bc9-a813-3f4b57e51d27"},"_deposit":{"created_by":14,"id":"6230","owners":[14],"pid":{"revision_id":0,"type":"depid","value":"6230"},"status":"published"},"_oai":{"id":"oai:kyutech.repo.nii.ac.jp:00006230","sets":["8:24"]},"author_link":["25644","25645","25646","6037"],"control_number":"6230","item_21_alternative_title_18":{"attribute_name":"その他のタイトル","attribute_value_mlt":[{"subitem_alternative_title":"An approximation algorithm for the maximum induced matching problem on C5-free regular graphs","subitem_alternative_title_language":"en"}]},"item_21_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2019-09-01","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"9","bibliographicPageEnd":"1149","bibliographicPageStart":"1142","bibliographicVolumeNumber":"E102-A","bibliographic_titles":[{"bibliographic_title":"IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences","bibliographic_titleLang":"en"}]}]},"item_21_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"In this paper, we investigate the maximum induced matching problem (MaxIM) on C5-free d-regular graphs. The previously known best approximation ratio for MaxIM on C5-free d-regular graphs is $\\left(\\frac{3d}{4}-\\frac{1}{8}+\\frac{3}{16d-8}\\right)$. In this paper, we design a $\\left(\\frac{2d}{3}+\\frac{1}{3}\\right)$-approximation algorithm, whose approximation ratio is strictly smaller/better than the previous one when d≥6.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_21_description_60":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"subitem_description":"Journal Article","subitem_description_type":"Other"}]},"item_21_link_62":{"attribute_name":"研究者情報","attribute_value_mlt":[{"subitem_link_url":"https://hyokadb02.jimu.kyutech.ac.jp/html/233_ja.html"}]},"item_21_publisher_7":{"attribute_name":"出版社","attribute_value_mlt":[{"subitem_publisher":"電子情報通信学会","subitem_publisher_language":"ja"}]},"item_21_relation_12":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isIdenticalTo","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doi.org/10.1587/transfun.E102.A.1142","subitem_relation_type_select":"DOI"}}]},"item_21_rights_13":{"attribute_name":"著作権関連情報","attribute_value_mlt":[{"subitem_rights":"Copyright (c) 2019 The Institute of Electronics, Information and Communication Engineers"}]},"item_21_select_59":{"attribute_name":"査読の有無","attribute_value_mlt":[{"subitem_select_item":"yes"}]},"item_21_source_id_10":{"attribute_name":"NCID","attribute_value_mlt":[{"subitem_source_identifier":"AA10826261","subitem_source_identifier_type":"NCID"}]},"item_21_source_id_8":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0916-8516","subitem_source_identifier_type":"PISSN"},{"subitem_source_identifier":"1745-1345","subitem_source_identifier_type":"EISSN"}]},"item_21_subject_16":{"attribute_name":"日本十進分類法","attribute_value_mlt":[{"subitem_subject":"548","subitem_subject_scheme":"NDC"}]},"item_21_text_28":{"attribute_name":"論文ID（連携）","attribute_value_mlt":[{"subitem_text_value":"10347275"}]},"item_21_text_63":{"attribute_name":"連携ID","attribute_value_mlt":[{"subitem_text_value":"7935"}]},"item_21_version_type_58":{"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":"Asahiro,  Yuichi","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Lin, Guohui","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Liu, Zhilong","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorAffiliations":[{"affiliationNames":[{}]}],"creatorNames":[{"creatorName":"Miyano, Eiji","creatorNameLang":"en"},{"creatorName":"宮野, 英次","creatorNameLang":"ja"},{"creatorName":"ミヤノ, エイジ","creatorNameLang":"ja-Kana"}],"familyNames":[{},{},{}],"givenNames":[{},{},{}],"nameIdentifiers":[{},{},{},{},{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2019-11-19"}],"displaytype":"detail","filename":"transfun.E102.A.1142.pdf","filesize":[{"value":"1.9 MB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"transfun.E102.A.1142.pdf","url":"https://kyutech.repo.nii.ac.jp/record/6230/files/transfun.E102.A.1142.pdf"},"version_id":"7f97b465-1c89-4140-b870-31d4bf114069"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"induced matching problem","subitem_subject_scheme":"Other"},{"subitem_subject":"C5-free regular graph","subitem_subject_scheme":"Other"},{"subitem_subject":"approximation algorithm","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"An Approximation Algorithm for the Maximum Induced Matching Problem on C5-Free Regular Graphs","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"An Approximation Algorithm for the Maximum Induced Matching Problem on C5-Free Regular Graphs","subitem_title_language":"en"}]},"item_type_id":"21","owner":"14","path":["24"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2019-11-19"},"publish_date":"2019-11-19","publish_status":"0","recid":"6230","relation_version_is_last":true,"title":["An Approximation Algorithm for the Maximum Induced Matching Problem on C5-Free Regular Graphs"],"weko_creator_id":"14","weko_shared_id":-1},"updated":"2023-12-12T01:45:53.971093+00:00"}