{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00217766","sets":["1164:2592:10824:10923"]},"path":["10923"],"owner":"44499","recid":"217766","title":["Transportation Problem on a Graph"],"pubdate":{"attribute_name":"公開日","attribute_value":"2022-05-12"},"_buckets":{"deposit":"5feb2a97-f548-43e2-bfb9-21815e31b309"},"_deposit":{"id":"217766","pid":{"type":"depid","value":"217766","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"Transportation Problem on a Graph","author_link":["564838","564837"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Transportation Problem on a Graph"},{"subitem_title":"Transportation Problem on a Graph","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2022-05-12","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Kanazawa University"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Kanazawa University","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"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/217766/files/IPSJ-AL22188003.pdf","label":"IPSJ-AL22188003.pdf"},"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL22188003.pdf","filesize":[{"value":"1.1 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_login","version_id":"1f43fbf7-6079-4146-ac2a-9290c53be6e2","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2022 by the Institute of Electronics, Information and Communication Engineers This SIG report is only available to those in membership of the SIG."}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Tetsuo, Asano"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Tetsuo, Asano","creatorNameLang":"en"}],"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":"We consider a transportation problem defined on a node-weighted undirected graph. Weight is positive if the amount of commodity is stored at a node, and negative if the amount is needed at the node. We want to meet all demands by transporting commodities using vehicles prepared either at nodes or edges which only travel to and from neighbors. In a trip from a node to a neighbor we can send commodities and also bring back some other commodities. Problem is to decide whether we can meet all demands by carrying out a set of trips in a few rounds. We define three different schemes to solve the problem and examine their performances. We present a polynomial-time algorithm for deciding whether there is a single round of trips using one vehicle at each node that meet all demands for one-commodity case. Although extension to multi-commodity case is unknown, we can also extend it to multiple rounds as far as the number of iterations is bounded by a constant.","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"We consider a transportation problem defined on a node-weighted undirected graph. Weight is positive if the amount of commodity is stored at a node, and negative if the amount is needed at the node. We want to meet all demands by transporting commodities using vehicles prepared either at nodes or edges which only travel to and from neighbors. In a trip from a node to a neighbor we can send commodities and also bring back some other commodities. Problem is to decide whether we can meet all demands by carrying out a set of trips in a few rounds. We define three different schemes to solve the problem and examine their performances. We present a polynomial-time algorithm for deciding whether there is a single round of trips using one vehicle at each node that meet all demands for one-commodity case. Although extension to multi-commodity case is unknown, we can also extend it to multiple rounds as far as the number of iterations is bounded by a constant.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"8","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2022-05-12","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"3","bibliographicVolumeNumber":"2022-AL-188"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":217766,"updated":"2025-01-19T15:22:25.412112+00:00","links":{},"created":"2025-01-19T01:18:13.911654+00:00"}