{"created":"2023-07-27T06:58:19.190305+00:00","id":56526,"links":{},"metadata":{"_buckets":{"deposit":"7945cfe4-cd48-490d-848b-d9c57f9c8e4a"},"_deposit":{"created_by":18,"id":"56526","owners":[18],"pid":{"revision_id":0,"type":"depid","value":"56526"},"status":"published"},"_oai":{"id":"oai:kanazawa-u.repo.nii.ac.jp:00056526","sets":["934:935:936"]},"author_link":["99048","99049","97040"],"item_4_biblio_info_8":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2011","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"5","bibliographicPageEnd":"586","bibliographicPageStart":"569","bibliographicVolumeNumber":"15","bibliographic_titles":[{"bibliographic_title":"Journal of Graph Algorithms and Applications"}]}]},"item_4_creator_33":{"attribute_name":"著者別表示","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"浅野, 哲夫"}],"nameIdentifiers":[{},{}]}]},"item_4_description_21":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"Constant-work-space algorithms model computation when space is at a premium: the input is given as a read-only array that allows random ac- cess to its entries, and the algorithm may use constantly many additional registers of O(logn) bits each, where n denotes the input size. We present such algorithms for two restricted variants of the shortest path problem. First, we describe how to report a simple path between two arbitrary nodes in a given tree. Using a technique called \"computing instead of storing\", we obtain a naive algorithm that needs quadratic time and a constant number of additional registers. We then show how to improve the running time to linear by applying a technique named \"simulated parallelization\". Second, we show how to compute a shortest geodesic path between two points in a simple polygon in quadratic time and with constant work-space.","subitem_description_type":"Abstract"}]},"item_4_description_5":{"attribute_name":"提供者所属","attribute_value_mlt":[{"subitem_description":"金沢大学","subitem_description_type":"Other"}]},"item_4_identifier_registration":{"attribute_name":"ID登録","attribute_value_mlt":[{"subitem_identifier_reg_text":"10.24517/00062800","subitem_identifier_reg_type":"JaLC"}]},"item_4_publisher_17":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Brown University"}]},"item_4_relation_12":{"attribute_name":"DOI","attribute_value_mlt":[{"subitem_relation_type":"isIdenticalTo","subitem_relation_type_id":{"subitem_relation_type_id_text":"10.7155/jgaa.00240","subitem_relation_type_select":"DOI"}}]},"item_4_relation_28":{"attribute_name":"関連URI","attribute_value_mlt":[{"subitem_relation_name":[{"subitem_relation_name_text":"https://www.brown.edu/"}],"subitem_relation_type_id":{"subitem_relation_type_id_text":"https://www.brown.edu/","subitem_relation_type_select":"URI"}},{"subitem_relation_name":[{"subitem_relation_name_text":"http://jgaa.info/getPaper?id=240"}],"subitem_relation_type_id":{"subitem_relation_type_id_text":"http://jgaa.info/getPaper?id=240","subitem_relation_type_select":"URI"}}]},"item_4_rights_23":{"attribute_name":"権利","attribute_value_mlt":[{"subitem_rights":"Copyright © Brown University, Journal of Graph Algorithms and Applications"}]},"item_4_source_id_9":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1526-1719","subitem_source_identifier_type":"ISSN"}]},"item_4_version_type_25":{"attribute_name":"著者版フラグ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_970fb48d4fbd8a85","subitem_version_type":"VoR"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Asano, Tetsuo"}],"nameIdentifiers":[{},{}]},{"creatorNames":[{"creatorName":"Mulzer, Wolfgang"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Wang, Yajun"}],"nameIdentifiers":[{}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2021-07-05"}],"displaytype":"detail","filename":"TE-PR-ASANO-T-569.pdf","filesize":[{"value":"1.6 MB"}],"format":"application/pdf","licensetype":"license_11","mimetype":"application/pdf","url":{"label":"TE-PR-ASANO-T-569.pdf","url":"https://kanazawa-u.repo.nii.ac.jp/record/56526/files/TE-PR-ASANO-T-569.pdf"},"version_id":"f69ff509-e1ae-42f2-8e3f-8f9249164be3"}]},"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":"Constant-work-space algorithms for shortest paths in trees and simple polygons","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Constant-work-space algorithms for shortest paths in trees and simple polygons"}]},"item_type_id":"4","owner":"18","path":["936"],"pubdate":{"attribute_name":"公開日","attribute_value":"2021-07-05"},"publish_date":"2021-07-05","publish_status":"0","recid":"56526","relation_version_is_last":true,"title":["Constant-work-space algorithms for shortest paths in trees and simple polygons"],"weko_creator_id":"18","weko_shared_id":-1},"updated":"2023-07-27T15:14:42.493208+00:00"}