{"created":"2021-03-01T06:20:10.731546+00:00","id":13171,"links":{},"metadata":{"_buckets":{"deposit":"d8e9449e-0271-413a-ac93-94ca8adae358"},"_deposit":{"id":"13171","owners":[],"pid":{"revision_id":0,"type":"depid","value":"13171"},"status":"published"},"_oai":{"id":"oai:nagoya.repo.nii.ac.jp:00013171"},"item_10_biblio_info_6":{"attribute_name":"\u66f8\u8a8c\u60c5\u5831","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2006-05-01","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"5","bibliographicPageEnd":"1427","bibliographicPageStart":"1425","bibliographicVolumeNumber":"E89-A","bibliographic_titles":[{"bibliographic_title":"IEICE transactions on fundamentals of electronics, communications and computer sciences"}]}]},"item_10_description_4":{"attribute_name":"\u6284\u9332","attribute_value_mlt":[{"subitem_description":"For a property \u03c0 on graphs, the edge-contraction problem with respect to \u03c0 is defined as a problem of finding a set of edges of minimum cardinality whose contraction results in a graph satisfying the property \u03c0. This paper gives a lower bound for the approximation ratio for the problem for any property \u03c0 that is hereditary on contractions and determined by biconnected components.","subitem_description_type":"Abstract"}]},"item_10_identifier_60":{"attribute_name":"URI","attribute_value_mlt":[{"subitem_identifier_type":"URI","subitem_identifier_uri":"http://www.ieice.org/jpn/trans_online/index.html"},{"subitem_identifier_type":"HDL","subitem_identifier_uri":"http://hdl.handle.net/2237/15066"}]},"item_10_publisher_32":{"attribute_name":"\u51fa\u7248\u8005","attribute_value_mlt":[{"subitem_publisher":"Institute of Electronics, Information and Communication Engineers"}]},"item_10_rights_12":{"attribute_name":"\u6a29\u5229","attribute_value_mlt":[{"subitem_rights":"Copyright (C) 2006 IEICE"}]},"item_10_select_15":{"attribute_name":"\u8457\u8005\u7248\u30d5\u30e9\u30b0","attribute_value_mlt":[{"subitem_select_item":"publisher"}]},"item_10_source_id_7":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0916-8508","subitem_source_identifier_type":"ISSN"}]},"item_creator":{"attribute_name":"\u8457\u8005","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"OTSUKI, Hideaki"}],"nameIdentifiers":[{"nameIdentifier":"41561","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"HIRATA, Tomio"}],"nameIdentifiers":[{"nameIdentifier":"41562","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"\u30d5\u30a1\u30a4\u30eb\u60c5\u5831","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2018-02-20"}],"displaytype":"detail","filename":"465.pdf","filesize":[{"value":"106.3 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"465.pdf","url":"https://nagoya.repo.nii.ac.jp/record/13171/files/465.pdf"},"version_id":"5e5eda06-1fa6-4ecd-a77b-1a6ff9897900"}]},"item_keyword":{"attribute_name":"\u30ad\u30fc\u30ef\u30fc\u30c9","attribute_value_mlt":[{"subitem_subject":"edge-contraction problem","subitem_subject_scheme":"Other"},{"subitem_subject":"NP-hard","subitem_subject_scheme":"Other"},{"subitem_subject":"approximation algorithm","subitem_subject_scheme":"Other"},{"subitem_subject":"approximability","subitem_subject_scheme":"Other"},{"subitem_subject":"connected vertex cover problem","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"\u8a00\u8a9e","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"\u8cc7\u6e90\u30bf\u30a4\u30d7","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Inapproximability of the Edge-Contraction Problem","item_titles":{"attribute_name":"\u30bf\u30a4\u30c8\u30eb","attribute_value_mlt":[{"subitem_title":"Inapproximability of the Edge-Contraction Problem"}]},"item_type_id":"10","owner":"1","path":["320/321/322"],"pubdate":{"attribute_name":"\u516c\u958b\u65e5","attribute_value":"2011-07-13"},"publish_date":"2011-07-13","publish_status":"0","recid":"13171","relation_version_is_last":true,"title":["Inapproximability of the Edge-Contraction Problem"],"weko_creator_id":"1","weko_shared_id":null},"updated":"2021-03-01T18:36:49.040478+00:00"}