{"created":"2025-01-19T00:35:54.479390+00:00","updated":"2025-01-20T11:02:59.367468+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00164037","sets":["1164:2592:8452:8750"]},"path":["8750"],"owner":"11","recid":"164037","title":["最大重み極小セパレータ問題について"],"pubdate":{"attribute_name":"公開日","attribute_value":"2016-06-17"},"_buckets":{"deposit":"7d92b4af-6ef9-4ad7-b173-4640bda2aaea"},"_deposit":{"id":"164037","pid":{"type":"depid","value":"164037","revision_id":0},"owners":[11],"status":"published","created_by":11},"item_title":"最大重み極小セパレータ問題について","author_link":["322558","322562","322563","322565","322561","322559","322564","322560"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"最大重み極小セパレータ問題について"},{"subitem_title":"On the Maximum Weight Minimal Separator","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2016-06-17","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Department of Economic Engineering, Kyushu University"},{"subitem_text_value":"Department of Computing Science Algorithmic Systems, Utrecht University"},{"subitem_text_value":"Department of Computing Science Algorithmic Systems, Utrecht University"},{"subitem_text_value":"Department of Economic Engineering, Kyushu University"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Department of Economic Engineering, Kyushu University","subitem_text_language":"en"},{"subitem_text_value":"Department of Computing Science Algorithmic Systems, Utrecht University","subitem_text_language":"en"},{"subitem_text_value":"Department of Computing Science Algorithmic Systems, Utrecht University","subitem_text_language":"en"},{"subitem_text_value":"Department of Economic Engineering, Kyushu 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/164037/files/IPSJ-AL16158012.pdf","label":"IPSJ-AL16158012.pdf"},"date":[{"dateType":"Available","dateValue":"2018-06-17"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL16158012.pdf","filesize":[{"value":"174.1 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":"223dfe73-9611-43cf-aac0-b4b718e13ce1","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2016 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"土中, 哲秀"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Bodlaender, Hans L."}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Zanden, T.C. van der"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"小野, 廣隆"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Tesshu, Hanaka","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Hans, L. Bodlaender","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"T.C., van der Zanden","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Hirotaka, Ono","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":"無向連結グラフ G = (V,E) において，2 点 s,t が与えられたとき，s と t を分離する点部分集合を s-t セパレータという．特に，任意の真部分集合が s-t セパレータではないものを極小 s-t セパレータという．本研究では，点重み付きグラフに対して，重み最大の極小 s-t セパレータを発見する問題について考察する．まずこの問題が NP 困難であることを示した上で，木幅が tw 以下のグラフに対して，O*(9tw・W)- 時間で重み W の極小 s-t セパレータが存在するかどうかを判定する乱択アルゴリズムを提案する．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"Given an undirected and connected graph G = (V,E) and two vertices s, t ∈ V, a vertex subset S which separates s and t is called s-t separator. Additionally, S is called minimal s-t separator if no proper set of S separates s and t. In this pater, we consider finding a minimal s-t separator with maximum weight on a vertex-weighted graph. We firstly prove this problem is NP-hard. Then we propose an O*(9tw・W)-randomized algorithm to determine whether there exists a minimal s-t separator with weight W on a graph with bounded treewidth.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"7","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2016-06-17","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"12","bibliographicVolumeNumber":"2016-AL-158"}]},"relation_version_is_last":true,"weko_creator_id":"11"},"id":164037,"links":{}}