{"links":{},"id":233382,"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00233382","sets":["1164:2592:11452:11525"]},"path":["11525"],"owner":"44499","recid":"233382","title":["グラフ分解に基づく高性能なビール路クエリシステム"],"pubdate":{"attribute_name":"公開日","attribute_value":"2024-03-14"},"_buckets":{"deposit":"897066cb-c448-43b1-a89c-351d6ba2b338"},"_deposit":{"id":"233382","pid":{"type":"depid","value":"233382","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"グラフ分解に基づく高性能なビール路クエリシステム","author_link":["633809","633807","633806","633808"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"グラフ分解に基づく高性能なビール路クエリシステム"},{"subitem_title":"An efficient beer path query system based on graph decomposition","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2024-03-14","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"名古屋大学大学院情報学研究科"},{"subitem_text_value":"九州大学大学院システム情報科学研究院"},{"subitem_text_value":"名古屋大学大学院情報学研究科"},{"subitem_text_value":"東京大学大学院情報理工学系研究科"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Graduate School of Informatics, Nagoya University","subitem_text_language":"en"},{"subitem_text_value":"Faculty of Information Science and Electrical Engineering, Kyushu University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Informatics, Nagoya University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Information Science and Technology, The University of Tokyo","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"publish_status":"0","weko_shared_id":-1,"item_file_price":{"attribute_name":"Billing file","attribute_type":"file","attribute_value_mlt":[{"url":{"url":"https://ipsj.ixsq.nii.ac.jp/record/233382/files/IPSJ-AL24197007.pdf","label":"IPSJ-AL24197007.pdf"},"date":[{"dateType":"Available","dateValue":"2026-03-14"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL24197007.pdf","filesize":[{"value":"986.2 kB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"0ecb6071-9597-404f-af1b-c7728fd06c2b","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2024 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"杉山, 康恭"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"土中, 哲秀"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"小野, 廣隆"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"定兼, 邦彦"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8566","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"与えられた非負辺重み付きグラフ G と頂点部分集合 B⊆V(G)，2 頂点 s, t に対し，B 内の頂点を 1 回以上通る s-t 歩を s-t ビール路という．そして，s-t ビール路の全部の中での距離（重み和）の最小値を s-t ビール距離という．固定されたグラフについて，2 頂点 s, t を与えて s-t ビール距離を問うクエリはビール路クエリと呼ばれる．ビール路クエリを高速に解く既存アルゴリズムとして外平面的グラフと区間グラフを対象としたものが存在する．これに対し本研究では任意のグラフに適用できるプリプロセッシングアルゴリズムを提案する．提案アルゴリズムは外平面的グラフに対してはこれに特化した既存アルゴリズムと同じ計算複雑性を実現する．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Given an edge-weighted graph G with beer vertices B ⊆ V (G), a beer path between two vertices s and t is a path between s and t that visits at least one beer vertex in B, and the beer distance between two vertices is the shortest length of beer paths. For a weighted graph with a set B, a query that takes two vertices s,t and answers the beer distance between s and t is called the beer path query. In general, we often consider the preprocessing algorithms when we need to improve the query time. Efficient algorithms are known for beer path queries if G is outerplanar graphs or unweighted interval graphs. We propose preprocessing algorithms that can be applied to arbitrary graphs. Also, our algorithms realize the same computational complexity as existing algorithms for outerplanar graphs if we specialize in outerplanar graphs.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"2","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2024-03-14","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"7","bibliographicVolumeNumber":"2024-AL-197"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"created":"2025-01-19T01:34:47.458059+00:00","updated":"2025-01-19T10:07:05.247241+00:00"}