{"created":"2023-07-27T06:24:38.396872+00:00","id":7628,"links":{},"metadata":{"_buckets":{"deposit":"93da2a62-6ca2-4ca6-9f76-143a1beb3e43"},"_deposit":{"created_by":3,"id":"7628","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"7628"},"status":"published"},"_oai":{"id":"oai:kanazawa-u.repo.nii.ac.jp:00007628","sets":["934:935:936"]},"author_link":["10227","614"],"item_4_biblio_info_8":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"1999-01-15","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"1","bibliographicPageEnd":"77","bibliographicPageStart":"71","bibliographicVolumeNumber":"33","bibliographic_titles":[{"bibliographic_title":"Networks"}]}]},"item_4_description_21":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"We consider the problem of embedding graphs into hypercubes with minimal congestion. Kim and Lai showed that for a given N-vertex graph G and a hypercube it is NP-complete to determine whether G is embeddable in the hypercube with unit congestion, but G can be embedded with unit congestion in a hypercube of dimension 6[log N] if the maximum degree of a vertex in G is no more than 6[log N]. Bhatt et al. showed that every N-vertex binary tree can be embedded in a hypercube of dimension [log N] with O(1) congestion. In this paper, we extend the results above and show the following : (1) Every N-vertex graph G can be embedded with unit congestion in a hypercube of dimension 2[log N] if the maximum degree of a vertex in G is no more than 2[log N], and (2) every N-vertex binary tree can be embedded in a hypercube of dimension [log N] with congestion at most 5. The former answers a question posed by Kim and Lai. The latter is the first result that shows a simple embedding of a binary tree into an optimal-sized hypercube with an explicit small congestion of 5. This partially answers a question posed by Bhatt et al. The embeddings proposed here are quite simple and can be constructed in polynomial time. © 1999 John Wiley & Sons, Inc. Networks 33: 71-77, 1999.","subitem_description_type":"Abstract"}]},"item_4_description_5":{"attribute_name":"提供者所属","attribute_value_mlt":[{"subitem_description":"金沢大学大学院自然科学研究科知能情報・数理","subitem_description_type":"Other"},{"subitem_description":"金沢大学工学部","subitem_description_type":"Other"}]},"item_4_publisher_17":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"John Wiley & Sons"}]},"item_4_relation_12":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"https://doi.org/10.1002/(sici)1097-0037(199901)33:1<71::aid-net5>3.0.co;2-3","subitem_relation_type_select":"DOI"}}]},"item_4_source_id_9":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0028-3045","subitem_source_identifier_type":"ISSN"}]},"item_4_version_type_25":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_ab4af688f83e57aa","subitem_version_type":"AM"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Matsubayashi, Akira"}],"nameIdentifiers":[{},{},{}]},{"creatorNames":[{"creatorName":"Ueno, Shuichi"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2017-10-03"}],"displaytype":"detail","filename":"TE-PR-MATSUBAYASI-A-71.pdf","filesize":[{"value":"117.6 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"TE-PR-MATSUBAYASI-A-71.pdf","url":"https://kanazawa-u.repo.nii.ac.jp/record/7628/files/TE-PR-MATSUBAYASI-A-71.pdf"},"version_id":"251f3336-3b33-437f-9aeb-788b24b05e5a"}]},"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":"Small congestion embedding of graphs into hypercubes","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Small congestion embedding of graphs into hypercubes"}]},"item_type_id":"4","owner":"3","path":["936"],"pubdate":{"attribute_name":"公開日","attribute_value":"2017-10-03"},"publish_date":"2017-10-03","publish_status":"0","recid":"7628","relation_version_is_last":true,"title":["Small congestion embedding of graphs into hypercubes"],"weko_creator_id":"3","weko_shared_id":3},"updated":"2023-07-27T11:10:18.793927+00:00"}