ログイン
言語:

WEKO3

  • トップ
  • ランキング
To
lat lon distance
To

Field does not validate



インデックスリンク

インデックスツリー

メールアドレスを入力してください。

WEKO

One fine body…

WEKO

One fine body…

アイテム

{"_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": ["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\u0027s 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\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_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", "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_note", "mimetype": "application/pdf", "size": 236100.0, "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"], "permalink_uri": "http://hdl.handle.net/2237/15063", "pubdate": {"attribute_name": "PubDate", "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": -1}
  1. B200 工学部/工学研究科
  2. B200a 雑誌掲載論文
  3. 学術雑誌

On Approximation Algorithms for Coloring k-Colorable Graphs

http://hdl.handle.net/2237/15063
http://hdl.handle.net/2237/15063
50383c2f-b311-4817-b5ac-23d1cd0f6a3b
名前 / ファイル ライセンス アクション
462.pdf 462.pdf (236.1 kB)
Item type 学術雑誌論文 / Journal Article(1)
公開日 2011-07-13
タイトル
タイトル On Approximation Algorithms for Coloring k-Colorable Graphs
言語 en
著者 XIE, Xuzhen

× XIE, Xuzhen

WEKO 41552

en XIE, Xuzhen

Search repository
ONO, Takao

× ONO, Takao

WEKO 41553

en ONO, Takao

Search repository
HIRATA, Tomio

× HIRATA, Tomio

WEKO 41554

en HIRATA, Tomio

Search repository
アクセス権
アクセス権 open access
アクセス権URI http://purl.org/coar/access_right/c_abf2
権利
言語 en
権利情報 Copyright (C) 2003 IEICE
キーワード
主題Scheme Other
主題 graph coloring
キーワード
主題Scheme Other
主題 approximation algorithms
キーワード
主題Scheme Other
主題 NP-hard
キーワード
主題Scheme Other
主題 maximum degree
抄録
内容記述 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.
言語 en
内容記述タイプ Abstract
出版者
言語 en
出版者 Institute of Electronics, Information and Communication Engineers
言語
言語 eng
資源タイプ
資源タイプresource http://purl.org/coar/resource_type/c_6501
タイプ journal article
出版タイプ
出版タイプ VoR
出版タイプResource http://purl.org/coar/version/c_970fb48d4fbd8a85
関連情報
関連タイプ isVersionOf
識別子タイプ URI
関連識別子 http://www.ieice.org/jpn/trans_online/index.html
ISSN
収録物識別子タイプ PISSN
収録物識別子 0916-8508
書誌情報 en : IEICE transactions on fundamentals of electronics, communications and computer sciences

巻 E86-A, 号 5, p. 1046-1051, 発行日 2003-05-01
著者版フラグ
値 publisher
URI
識別子 http://www.ieice.org/jpn/trans_online/index.html
識別子タイプ URI
URI
識別子 http://hdl.handle.net/2237/15063
識別子タイプ HDL
戻る
0
views
See details
Views

Versions

Ver.1 2021-03-01 18:36:54.751454
Show All versions

Share

Mendeley Twitter Facebook Print Addthis

Cite as

エクスポート

OAI-PMH
  • OAI-PMH JPCOAR
  • OAI-PMH DublinCore
  • OAI-PMH DDI
Other Formats
  • JSON
  • BIBTEX

Confirm


Powered by WEKO3


Powered by WEKO3