{"created":"2021-03-01T06:20:10.539543+00:00","id":13168,"links":{},"metadata":{"_buckets":{"deposit":"a6fe5e49-272e-405f-8c48-792f34f18b34"},"_deposit":{"id":"13168","owners":[],"pid":{"revision_id":0,"type":"depid","value":"13168"},"status":"published"},"_oai":{"id":"oai:nagoya.repo.nii.ac.jp:00013168","sets":["320:321:322"]},"author_link":["41552","41553","41554"],"item_10_biblio_info_6":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2003-05-01","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"5","bibliographicPageEnd":"1051","bibliographicPageStart":"1046","bibliographicVolumeNumber":"E86-A","bibliographic_titles":[{"bibliographic_title":"IEICE transactions on fundamentals of electronics, communications and computer sciences","bibliographic_titleLang":"en"}]}]},"item_10_description_4":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"Karger, Motwani and Sudan presented a graph coloring algorithm based on semidefinite programming, which colors any k-colorable graph with maximum degree Δ using Õ(Δ^1-2/k) colors. This algorithm leads to an algorithm for k-colorable graph using Õ(n ^1-3/^(k+1)) colors. This improved Wigderson's algorithm, which uses O(n^1-1/^(k-1)) colors, containing as a subroutine an algorithm using (Δ+1) colors for graphs with maximum degree Δ. It is easy to imagine that an algorithm which uses less colors in terms of Δ leads to an algorithm which uses less colors in terms of n. In this paper, we consider this influence assuming that we have an algorithm which uses Õ(Δ^1-x/k) colors for 2<x<3. Specifically, we will show that the algorithms of Karger et al., of Blum and Karger and of Halperin et al. can be improved under this assumption.","subitem_description_language":"en","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/15063"}]},"item_10_publisher_32":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Institute of Electronics, Information and Communication Engineers","subitem_publisher_language":"en"}]},"item_10_relation_43":{"attribute_name":"関連情報","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"http://www.ieice.org/jpn/trans_online/index.html","subitem_relation_type_select":"URI"}}]},"item_10_rights_12":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"Copyright (C) 2003 IEICE","subitem_rights_language":"en"}]},"item_10_select_15":{"attribute_name":"著者版フラグ","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":"PISSN"}]},"item_1615787544753":{"attribute_name":"出版タイプ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_access_right":{"attribute_name":"アクセス権","attribute_value_mlt":[{"subitem_access_right":"open access","subitem_access_right_uri":"http://purl.org/coar/access_right/c_abf2"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"XIE, Xuzhen","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"41552","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"ONO, Takao","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"41553","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"HIRATA, Tomio","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"41554","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2018-02-20"}],"displaytype":"detail","filename":"462.pdf","filesize":[{"value":"236.1 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"462.pdf","objectType":"fulltext","url":"https://nagoya.repo.nii.ac.jp/record/13168/files/462.pdf"},"version_id":"38ce3096-341f-4169-bb50-8747ff7a3be1"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"graph coloring","subitem_subject_scheme":"Other"},{"subitem_subject":"approximation algorithms","subitem_subject_scheme":"Other"},{"subitem_subject":"NP-hard","subitem_subject_scheme":"Other"},{"subitem_subject":"maximum degree","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":"On Approximation Algorithms for Coloring k-Colorable Graphs","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"On Approximation Algorithms for Coloring k-Colorable Graphs","subitem_title_language":"en"}]},"item_type_id":"10","owner":"1","path":["322"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2011-07-13"},"publish_date":"2011-07-13","publish_status":"0","recid":"13168","relation_version_is_last":true,"title":["On Approximation Algorithms for Coloring k-Colorable Graphs"],"weko_creator_id":"1","weko_shared_id":-1},"updated":"2023-01-16T04:00:16.165055+00:00"}