{"_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"}, "item_10_biblio_info_6": {"attribute_name": "\u66f8\u8a8c\u60c5\u5831", "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"}]}]}, "item_10_description_4": {"attribute_name": "\u6284\u9332", "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 \u0394 using \u00d5(\u0394^1-2/k) colors. This algorithm leads to an algorithm for k-colorable graph using \u00d5(n ^1-3/^(k+1)) colors. This improved Wigderson\u0027s algorithm, which uses O(n^1-1/^(k-1)) colors, containing as a subroutine an algorithm using (\u0394+1) colors for graphs with maximum degree \u0394. It is easy to imagine that an algorithm which uses less colors in terms of \u0394 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 \u00d5(\u0394^1-x/k) colors for 2\u003cx\u003c3. 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_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": "\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) 2003 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": "XIE, Xuzhen"}], "nameIdentifiers": [{"nameIdentifier": "41552", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "ONO, Takao"}], "nameIdentifiers": [{"nameIdentifier": "41553", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "HIRATA, Tomio"}], "nameIdentifiers": [{"nameIdentifier": "41554", "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", "download_preview_message": "", "file_order": 0, "filename": "462.pdf", "filesize": [{"value": "236.1 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 236100.0, "url": {"label": "462.pdf", "url": "https://nagoya.repo.nii.ac.jp/record/13168/files/462.pdf"}, "version_id": "38ce3096-341f-4169-bb50-8747ff7a3be1"}]}, "item_keyword": {"attribute_name": "\u30ad\u30fc\u30ef\u30fc\u30c9", "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": "\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": "On Approximation Algorithms for Coloring k-Colorable Graphs", "item_titles": {"attribute_name": "\u30bf\u30a4\u30c8\u30eb", "attribute_value_mlt": [{"subitem_title": "On Approximation Algorithms for Coloring k-Colorable Graphs"}]}, "item_type_id": "10", "owner": "1", "path": ["320/321/322"], "permalink_uri": "http://hdl.handle.net/2237/15063", "pubdate": {"attribute_name": "\u516c\u958b\u65e5", "attribute_value": "2011-07-13"}, "publish_date": "2011-07-13", "publish_status": "0", "recid": "13168", "relation": {}, "relation_version_is_last": true, "title": ["On Approximation Algorithms for Coloring k-Colorable Graphs"], "weko_shared_id": null}