{"created":"2023-05-15T15:30:08.250637+00:00","id":2613,"links":{},"metadata":{"_buckets":{"deposit":"9b2ee221-5956-470d-8648-a6dde296336f"},"_deposit":{"created_by":17,"id":"2613","owners":[17],"pid":{"revision_id":0,"type":"depid","value":"2613"},"status":"published"},"_oai":{"id":"oai:barrel.repo.nii.ac.jp:00002613","sets":["4"]},"author_link":["5588","5589","5590"],"item_1_biblio_info_5":{"attribute_name":"bibliographic_information","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2008-03-15","bibliographicIssueDateType":"Issued"},"bibliographic_titles":[{"bibliographic_title":"Algorithmica","bibliographic_titleLang":"en"}]}]},"item_1_description_18":{"attribute_name":"抄録","attribute_value_mlt":[{"subitem_description":"Given an undirected multigraph G=(V,E), a family $\\mathcal{W}$ of areas W⊆V, and a target connectivity k≥1, we consider the problem of augmenting G by the smallest number of new edges so that the resulting graph has at least k edge-disjoint paths between v and W for every pair of a vertex v∈V and an area $W\\in \\mathcal{W}$ . So far this problem was shown to be NP-complete in the case of k=1 and polynomially solvable in the case of k=2. In this paper, we show that the problem for k≥3 can be solved in O(m+n(k 3+n 2)(p+kn+nlog n)log k+pkn 3log (n/k)) time, where n=|V|, m=|{{u,v}|(u,v)∈E}|, and $p=|\\mathcal{W}|$","subitem_description_language":"en","subitem_description_type":"Abstract"}]},"item_1_publisher_6":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Springer","subitem_publisher_language":"en"}]},"item_1_relation_8":{"attribute_name":"item_1_relation_8","attribute_value_mlt":[{"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"info:doi/10.1007/s00453-008-9178-y","subitem_relation_type_select":"DOI"}}]},"item_1_source_id_7":{"attribute_name":"ISSN / EISSN","attribute_value_mlt":[{"subitem_source_identifier":"1432-0541","subitem_source_identifier_type":"EISSN"}]},"item_1_subject_16":{"attribute_name":"日本十進分類法","attribute_value_mlt":[{"subitem_subject":"415","subitem_subject_language":"ja","subitem_subject_scheme":"NDC"}]},"item_1_subject_17":{"attribute_name":"NIIサブジェクト","attribute_value_mlt":[{"subitem_subject":"数学","subitem_subject_language":"ja","subitem_subject_scheme":"Other"}]},"item_1_version_type_15":{"attribute_name":"出版タイプ","attribute_value_mlt":[{"subitem_version_resource":"http://purl.org/coar/version/c_ab4af688f83e57aa","subitem_version_type":"AM"}]},"item_creator":{"attribute_name":"著者","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Ishii, Toshimasa","creatorNameLang":"en","creatorNameType":"Personal"}],"nameIdentifiers":[{"nameIdentifier":"5588","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Akiyama, Yoko","creatorNameLang":"en","creatorNameType":"Personal"}],"nameIdentifiers":[{"nameIdentifier":"5589","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Nagamochi, Hiroshi","creatorNameLang":"en","creatorNameType":"Personal"}],"nameIdentifiers":[{"nameIdentifier":"5590","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2016-01-23"}],"displaytype":"detail","filename":"Ishii_Algorithmica.pdf","filesize":[{"value":"366.7 kB"}],"format":"application/pdf","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"Ishii_Algorithmica.pdf","url":"https://barrel.repo.nii.ac.jp/record/2613/files/Ishii_Algorithmica.pdf"},"version_id":"c1b29286-7909-4ccf-a0f6-96dfb80ad788"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"Undirected graph","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Connectivity augmentation problem","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Edge-connectivity","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Node-to-area connectivity","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Polynomial time deterministic algorithm","subitem_subject_language":"en","subitem_subject_scheme":"Other"},{"subitem_subject":"Edge-splitting","subitem_subject_language":"en","subitem_subject_scheme":"Other"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"item_resource_type":{"attribute_name":"item_resource_type","attribute_value_mlt":[{"resourcetype":"journal article","resourceuri":"http://purl.org/coar/resource_type/c_6501"}]},"item_title":"Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs","subitem_title_language":"en"}]},"item_type_id":"1","owner":"17","path":["4"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2009-08-10"},"publish_date":"2009-08-10","publish_status":"0","recid":"2613","relation_version_is_last":true,"title":["Minimum augmentation of edge-connectivity between vertices and sets of vertices in undirected graphs"],"weko_creator_id":"17","weko_shared_id":-1},"updated":"2025-02-17T07:29:19.733844+00:00"}