{"created":"2021-03-01T05:52:57.388391+00:00","id":1242,"links":{},"metadata":{"_buckets":{"deposit":"93783b85-d38b-4d0a-a2e9-9ddfd232e02e"},"_deposit":{"id":"1242","owners":[],"pid":{"revision_id":0,"type":"depid","value":"1242"},"status":"published"},"_oai":{"id":"oai:repository.nii.ac.jp:00001242","sets":["136"]},"author_link":[],"control_number":"1242","item_5_biblio_info_30":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2008-03-31","bibliographicIssueDateType":"Issued"},"bibliographicPageEnd":"9","bibliographicPageStart":"1","bibliographic_titles":[{"bibliographic_title":"NIIテクニカル・レポート","bibliographic_titleLang":"ja"},{"bibliographic_title":"NII Technical Report","bibliographic_titleLang":"en"}]}]},"item_5_description_28":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"The shortest path problem is one of the most fundamental problems in computer science. Although several quasi linear time algorithms have been proposed, even an optimal algorithm does not terminate in sufficiently short time for large-scale networks, such as web networks and road networks. An approach to solving this problem is to construct data structures that enable us to find solutions in a short time. This approach is efficient for applications in which the networks are fixed and we have to answer possibly many questions in a short time, such as in car navigation systems. In this paper, we propose the levelwise mesh sparsification method for the problem. Several sparse networks are obtained by sparsifying the original network, and the shortest path problem is solved by finding the shortest path in these networks. The obtained networks are sparse and small, thus the computational time is short. Computational experiments on real world data show the efficiency of our method in terms of computational time and memory efficiency. Compared with existing approaches, the advantage of our method is that it can deal with negative costs and time-dependent costs, and uses only a small amount of memory.","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_5_identifier_registration":{"attribute_name":"ID登録","attribute_value_mlt":[{"subitem_identifier_reg_text":"10.20736/0000001242","subitem_identifier_reg_type":"JaLC"}]},"item_5_publisher_31":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"国立情報学研究所","subitem_publisher_language":"ja"}]},"item_5_source_id_32":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1346-5597","subitem_source_identifier_type":"ISSN"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"宮本, 裕一郎","creatorNameLang":"ja"},{"creatorName":"Miyamoto, Yuichiro","creatorNameLang":"en"}]},{"creatorNames":[{"creatorName":"宇野, 毅明","creatorNameLang":"ja"},{"creatorName":"Uno, Takeaki","creatorNameLang":"en"}]},{"creatorNames":[{"creatorName":"久保, 幹雄","creatorNameLang":"ja"},{"creatorName":"Kubo, Mikio","creatorNameLang":"en"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2019-03-12"}],"displaytype":"detail","filename":"08-004E.pdf","filesize":[{"value":"383.4 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"NII Technical Report (NII-2008-004E)：Levelwise Mesh Sparsification for Shortest Path Queries","url":"https://repository.nii.ac.jp/record/1242/files/08-004E.pdf"},"version_id":"d3213854-4492-40cc-a93e-bdf7aee567bc"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"テクニカルレポート","subitem_subject_language":"ja","subitem_subject_scheme":"Other"},{"subitem_subject":"Technical Report","subitem_subject_language":"en","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourcetype":"departmental bulletin paper","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"NII Technical Report (NII-2008-004E)：Levelwise Mesh Sparsification for Shortest Path Queries","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"NII Technical Report (NII-2008-004E)：Levelwise Mesh Sparsification for Shortest Path Queries","subitem_title_language":"en"}]},"item_type_id":"5","owner":"1","path":["136"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2019-03-12"},"publish_date":"2019-03-12","publish_status":"0","recid":"1242","relation_version_is_last":true,"title":["NII Technical Report (NII-2008-004E)：Levelwise Mesh Sparsification for Shortest Path Queries"],"weko_creator_id":"1","weko_shared_id":-1},"updated":"2023-01-05T06:20:53.765534+00:00"}