{"updated":"2025-01-22T16:25:24.489109+00:00","links":{},"id":31909,"created":"2025-01-18T23:01:07.763394+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00031909","sets":["1164:2592:2627:2629"]},"path":["2629"],"owner":"1","recid":"31909","title":["グラフに対する最大供給分割問題解法の性能評価"],"pubdate":{"attribute_name":"公開日","attribute_value":"2003-09-19"},"_buckets":{"deposit":"a53dc00d-2550-4903-b808-8c16919d72cd"},"_deposit":{"id":"31909","pid":{"type":"depid","value":"31909","revision_id":0},"owners":[1],"status":"published","created_by":1},"item_title":"グラフに対する最大供給分割問題解法の性能評価","author_link":["0","0"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"グラフに対する最大供給分割問題解法の性能評価"},{"subitem_title":"Experimental Evaluation of Algorithms for Maximum - Supply Partitioning of a Demand - Supply Graph","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2003-09-19","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 Engineering, Hiroshima University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Engineering, Hiroshima University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Engineering, Hiroshima University","subitem_text_language":"en"},{"subitem_text_value":"Graduate School of Engineering, Hiroshima University","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/31909/files/IPSJ-AL03091009.pdf"},"date":[{"dateType":"Available","dateValue":"2005-09-19"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL03091009.pdf","filesize":[{"value":"1.7 MB"}],"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":"19c64928-ebc0-4f82-8f18-7882dc270b8f","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2003 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"渡辺, 一哉"},{"creatorName":"高藤, 大介"},{"creatorName":"田岡, 智志"},{"creatorName":"渡邉, 敏正"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Kazuya, Watanabe","creatorNameLang":"en"},{"creatorName":"Daisuke, Takafuji","creatorNameLang":"en"},{"creatorName":"Satoshi, Taoka","creatorNameLang":"en"},{"creatorName":"Toshimasa, Watanabe","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_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"需要点集合Vdと供給点集合Vsの和集合である点集合  および無向辺集合Eを持つグラフG＝(Vd ∪ Vs E)  さらに各需要点vの需要量d(v)＞0  各供給点uの供給量s(u)＞0が与えられたとする. 各供給点uk(1≦k≦|Vs|)に対して  Σv∈Vdkb d(v)≦s(uk)かつVdk ∪{uk}のGでの誘導部分グラフが連結であるような  互いに素な需要点集合Vdkの族{Vdk|1≦k≦|Vs|}を求める. これらの需要点集合に属する需要点の需要量総和が最大となるような需要点集合族を求める問題を”グラフの最大供給分割問題”と呼ぶ. 本稿では  グラフの最大供給分割問題に対する既存の発見的解法と最適解法に着目し  提案する改良手法と共に計算機上で実装して  これらの性能を計算機実験により比較評価する.","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Let G＝(Vd ∪ Vs,E) be an undirected graph with two disjoint vertex sets: Vd of demand vertices and Vs of supply ones. Suppose that a positive value d(v) or s(v) is assigned to each demand or supply vertex v, respectively. Let Vd1,...,Vd|Vs| be a patition of Vd such that, for each uk ∈ Vs (1 ≦ k ≦ |Vs|), (i) the subgraph G[Vdk ∪{uk}] induced by Vdk ∪{uk} of G is connected, and (ii) Σv∈Vdk d(v) ≦ s(uk). The maximum-supply partition problem for a given demand-supply graph is to find such a partition with Σ1≦k≦|Vs| d(Vdk) being maximum, where d(Vdk)＝Σv∈Vdk d(v). This paper proposes improved versions of several known algorithms: one of them gives an optimum solution and all others produce heuristic ones, This performance is evaluated based on experimental results.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"66","bibliographic_titles":[{"bibliographic_title":"情報処理学会研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"59","bibliographicIssueDates":{"bibliographicIssueDate":"2003-09-19","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"92(2003-AL-091)","bibliographicVolumeNumber":"2003"}]},"relation_version_is_last":true,"weko_creator_id":"1"}}