{"created":"2023-07-27T06:25:10.784478+00:00","id":8371,"links":{},"metadata":{"_buckets":{"deposit":"1a907a14-0940-4a6f-9299-1a731997a998"},"_deposit":{"created_by":3,"id":"8371","owners":[3],"pid":{"revision_id":0,"type":"depid","value":"8371"},"status":"published"},"_oai":{"id":"oai:kanazawa-u.repo.nii.ac.jp:00008371","sets":["934:935:936"]},"author_link":["614","11706"],"item_4_biblio_info_8":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2011-09-09","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"39","bibliographicPageEnd":"5175","bibliographicPageStart":"5167","bibliographicVolumeNumber":"412","bibliographic_titles":[{"bibliographic_title":"Theoretical Computer Science"}]}]},"item_4_description_21":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"The minimum energy broadcast problem is to assign a transmission range to each node in an ad hoc wireless network to construct a spanning tree rooted at a given source node such that any non-root node resides within the transmission range of its parent. The objective is to minimize the total energy consumption, i.e., the sum of the δth powers of a transmission range (δ<1). In this paper, we consider the case that δ=2, and that nodes are located on a 2-dimensional rectangular grid. We prove that the minimum energy consumption for an n-node k×l-grid with n=kl and k≤l is at most nπ+O(n k0.68) and at least nπ+Ω(nk)-O(k). Our bounds close the previously known gap of upper and lower bounds for square grids. Moreover, our lower bound is n3-O(1) for 3≤k≤18, which matches a naive upper bound within a constant term for k≡0(mod3). © 2011 Elsevier B.V. All rights reserved.","subitem_description_type":"Abstract"}]},"item_4_publisher_17":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Elsevier B.V."}]},"item_4_relation_12":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"10.1016/j.tcs.2011.05.024","subitem_relation_type_select":"DOI"}}]},"item_4_relation_28":{"attribute_name":"関連URI","attribute_value_mlt":[{"subitem_relation_type_id":{"subitem_relation_type_id_text":"http://www.elsevier.com/locate/issn/03043975","subitem_relation_type_select":"URI"}}]},"item_4_source_id_11":{"attribute_name":"NCID","attribute_value_mlt":[{"subitem_source_identifier":"AA00862688","subitem_source_identifier_type":"NCID"}]},"item_4_source_id_9":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0304-3975","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":"Murata, Atsushi"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Matsubayashi, Akira"}],"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-MATSUBAYASHI-A-34[1].pdf","filesize":[{"value":"134.9 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"TE-PR-MATSUBAYASHI-A-34[1].pdf","url":"https://kanazawa-u.repo.nii.ac.jp/record/8371/files/TE-PR-MATSUBAYASHI-A-34[1].pdf"},"version_id":"cebda25e-4359-4bf2-a590-c61349a687e4"}]},"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":"Minimum energy broadcast on rectangular grid wireless networks","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Minimum energy broadcast on rectangular grid wireless networks"}]},"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":"8371","relation_version_is_last":true,"title":["Minimum energy broadcast on rectangular grid wireless networks"],"weko_creator_id":"3","weko_shared_id":-1},"updated":"2023-07-28T02:09:58.647025+00:00"}