{"created":"2021-03-01T06:05:35.457577+00:00","id":1907,"links":{},"metadata":{"_buckets":{"deposit":"40ddf62d-ee91-4fe1-af05-d9b527daec7b"},"_deposit":{"id":"1907","owners":[],"pid":{"revision_id":0,"type":"depid","value":"1907"},"status":"published"},"_oai":{"id":"oai:niigata-u.repo.nii.ac.jp:00001907"},"item_5_biblio_info_6":{"attribute_name":"\u66f8\u8a8c\u60c5\u5831","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"1997-04","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"4","bibliographicPageEnd":"657","bibliographicPageStart":"651","bibliographicVolumeNumber":"E80-A","bibliographic_titles":[{"bibliographic_title":"IEICE transactions on fundamentals of electronics, communications and computer sciences"},{"bibliographic_title":"IEICE transactions on fundamentals of electronics, communications and computer sciences","bibliographic_titleLang":"en"}]}]},"item_5_description_4":{"attribute_name":"\u6284\u9332","attribute_value_mlt":[{"subitem_description":"In this paper we extend the p-collection problem to a flow network with lower bounds, and call the extended problem the lower-bounded p-collection problem. First we discuss the complexity of this problem to show NP-hardness for a network with path structure. Next we present a linear time algorithm for the lower-bounded 1-collection problem in a network with tree structure, and a pseudo-polynomial time algorithm with dynamic programming type for the lower-bounded p-collection problem in a network with tree structure. Using the pseudo-polynomial time algorithm, we show an exponential algorithm, which is efficient in a connected network with few cycles, for the lower-bounded p-collection problem.","subitem_description_type":"Abstract"}]},"item_5_full_name_3":{"attribute_name":"\u8457\u8005\u5225\u540d","attribute_value_mlt":[{"nameIdentifiers":[{"nameIdentifier":"5597","nameIdentifierScheme":"WEKO"}],"names":[{"name":"\u4e2d\u91ce, \u656c\u4ecb"}]},{"nameIdentifiers":[{"nameIdentifier":"6172","nameIdentifierScheme":"WEKO"}],"names":[{"name":"\u4ed9\u77f3, \u6b63\u548c"}]}]},"item_5_publisher_7":{"attribute_name":"\u51fa\u7248\u8005","attribute_value_mlt":[{"subitem_publisher":"The Institute of Electronics, Information and Communication Engineers"}]},"item_5_relation_31":{"attribute_name":"\u7570\u7248\u3067\u3042\u308b","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"http://www.ieice.org/jpn/trans_online/","subitem_relation_type_select":"URI"}}]},"item_5_rights_15":{"attribute_name":"\u6a29\u5229","attribute_value_mlt":[{"subitem_rights":"copyright\u00a91997 IEICE"}]},"item_5_select_19":{"attribute_name":"\u8457\u8005\u7248\u30d5\u30e9\u30b0","attribute_value_mlt":[{"subitem_select_item":"publisher"}]},"item_5_source_id_11":{"attribute_name":"\u66f8\u8a8c\u30ec\u30b3\u30fc\u30c9ID","attribute_value_mlt":[{"subitem_source_identifier":"AA10826239","subitem_source_identifier_type":"NCID"}]},"item_5_source_id_9":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"09168508","subitem_source_identifier_type":"ISSN"}]},"item_creator":{"attribute_name":"\u8457\u8005","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Tamura, Hiroshi"}],"nameIdentifiers":[{"nameIdentifier":"6168","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Nakano, Keisuke"}],"nameIdentifiers":[{"nameIdentifier":"5597","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Sengoku, Masakazu"}],"nameIdentifiers":[{"nameIdentifier":"6170","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"\u30d5\u30a1\u30a4\u30eb\u60c5\u5831","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2019-07-29"}],"displaytype":"detail","filename":"e80-a_4_651.pdf","filesize":[{"value":"528.1 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"e80-a_4_651.pdf","url":"https://niigata-u.repo.nii.ac.jp/record/1907/files/e80-a_4_651.pdf"},"version_id":"87e89fd7-ea53-49ed-be5a-eaafde0fb886"}]},"item_keyword":{"attribute_name":"\u30ad\u30fc\u30ef\u30fc\u30c9","attribute_value_mlt":[{"subitem_subject":"location problem","subitem_subject_scheme":"Other"},{"subitem_subject":"network flows","subitem_subject_scheme":"Other"},{"subitem_subject":"NP-complete","subitem_subject_scheme":"Other"},{"subitem_subject":"optimization problem","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"\u8a00\u8a9e","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"\u8cc7\u6e90\u30bf\u30a4\u30d7","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"The p-Collection Problem in a Flow Network with Lower Bounds","item_titles":{"attribute_name":"\u30bf\u30a4\u30c8\u30eb","attribute_value_mlt":[{"subitem_title":"The p-Collection Problem in a Flow Network with Lower Bounds"},{"subitem_title":"The p-Collection Problem in a Flow Network with Lower Bounds","subitem_title_language":"en"}]},"item_type_id":"5","owner":"1","path":["453/454","423/424/425"],"pubdate":{"attribute_name":"\u516c\u958b\u65e5","attribute_value":"2008-07-28"},"publish_date":"2008-07-28","publish_status":"0","recid":"1907","relation_version_is_last":true,"title":["The p-Collection Problem in a Flow Network with Lower Bounds"],"weko_creator_id":"1","weko_shared_id":null},"updated":"2021-03-01T20:50:36.589415+00:00"}