{"created":"2023-05-15T12:36:16.310454+00:00","id":5506,"links":{},"metadata":{"_buckets":{"deposit":"83a9c185-2f4d-4045-9a05-eeee2af32992"},"_deposit":{"created_by":91,"id":"5506","owners":[91],"pid":{"revision_id":0,"type":"depid","value":"5506"},"status":"published"},"_oai":{"id":"oai:nitech.repo.nii.ac.jp:00005506","sets":["31"]},"author_link":["8720","8926","19407","8720","19409","8926"],"item_10001_biblio_info_28":{"attribute_name":"bibliographic_information","attribute_value_mlt":[{"bibliographicIssueDates":{"bibliographicIssueDate":"2010-06-28","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"31-33","bibliographicPageEnd":"2783","bibliographicPageStart":"2773","bibliographicVolumeNumber":"411","bibliographic_titles":[{"bibliographic_title":"Theoretical Computer Science","bibliographic_titleLang":"en"}]}]},"item_10001_description_36":{"attribute_name":"内容記述","attribute_value_mlt":[{"subitem_description":"Given an n-vertex directed graph G = (V;E) and a set R ⊆ V × V of requests,we consider to assign a set of edges to each vertex in G so that for every request(u; v) in R the union of the edge sets assigned to u and v contains a path fromu to v. The Minimum Certi cate Dispersal Problem (MCD) is defined as one tofind an assignment that minimizes the sum of the cardinalities of the edge setsassigned to each vertex. This problem has been shown to be NP-hard in general,though it is polynomially solvable for some restricted classes of graphs and restrictedrequest structures, such as bidirectional trees with requests of all pairsof vertices. In this paper, we give an advanced investigation about the difficultyof MCD by focusing on the relationship between its (in)approximability and requeststructures. We first show that MCD with general R has Θ(log n) lower andupper bounds on approximation ratio under the assumption P ?= NP. We thenassume R forms a clique structure, called Subset-Full, which is a natural settingin the context of the application. Interestingly, under this natural setting, MCDbecomes to be 2-approximable, though it has still no polynomial time approximationalgorithm whose factor better than 677=676 unless P = NP. Finally,we show that this approximation ratio can be improved to 3/2 for undirectedvariant of MCD with Subset-Full.","subitem_description_language":"en","subitem_description_type":"Other"}]},"item_10001_full_name_27":{"attribute_name":"著者別名","attribute_value_mlt":[{"familyNames":[{"familyName":"Izumi","familyNameLang":"en"},{"familyName":"泉","familyNameLang":"ja"},{"familyName":"イズミ","familyNameLang":"ja-Kana"}],"givenNames":[{"givenName":"Taisuke","givenNameLang":"en"},{"givenName":"泰介","givenNameLang":"ja"},{"givenName":"タイスケ","givenNameLang":"ja-Kana"}],"nameIdentifiers":[{"nameIdentifier":"8720","nameIdentifierScheme":"WEKO"},{"nameIdentifier":"1000020432461","nameIdentifierScheme":"NRID","nameIdentifierURI":"http://rns.nii.ac.jp/nr/1000020432461"}],"names":[{"name":"Izumi, Taisuke","nameLang":"en"},{"name":"泉, 泰介","nameLang":"ja"},{"name":"イズミ, タイスケ","nameLang":"ja-Kana"}]},{"nameIdentifiers":[{"nameIdentifier":"8926","nameIdentifierScheme":"WEKO"}],"names":[{"name":"和田, 幸一"}]}]},"item_10001_publisher_29":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"Elsevier BV","subitem_publisher_language":"en"}]},"item_10001_relation_34":{"attribute_name":"item_10001_relation_34","attribute_value_mlt":[{"subitem_relation_name":[{"subitem_relation_name_text":"10.1016/j.tcs.2010.03.029"}],"subitem_relation_type":"isVersionOf","subitem_relation_type_id":{"subitem_relation_type_id_text":"http://dx.doi.org/10.1016/j.tcs.2010.03.029","subitem_relation_type_select":"DOI"}}]},"item_10001_source_id_30":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"0304-3975","subitem_source_identifier_type":"ISSN"}]},"item_10001_source_id_32":{"attribute_name":"item_10001_source_id_32","attribute_value_mlt":[{"subitem_source_identifier":"AA00862688","subitem_source_identifier_type":"NCID"}]},"item_10001_version_type_33":{"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":"Izumi, Tomoko","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"19407","nameIdentifierScheme":"WEKO"}]},{"creatorAffiliations":[{"affiliationNameIdentifiers":[{"affiliationNameIdentifierScheme":"ISNI","affiliationNameIdentifierURI":"http://www.isni.org/isni/"}],"affiliationNames":[{"affiliationNameLang":"ja"}]}],"creatorNames":[{"creatorName":"Izumi, Taisuke","creatorNameLang":"en"},{"creatorName":"泉, 泰介","creatorNameLang":"ja"},{"creatorName":"イズミ, タイスケ","creatorNameLang":"ja-Kana"}],"familyNames":[{"familyName":"Izumi","familyNameLang":"en"},{"familyName":"泉","familyNameLang":"ja"},{"familyName":"イズミ","familyNameLang":"ja-Kana"}],"givenNames":[{"givenName":"Taisuke","givenNameLang":"en"},{"givenName":"泰介","givenNameLang":"ja"},{"givenName":"タイスケ","givenNameLang":"ja-Kana"}],"nameIdentifiers":[{"nameIdentifier":"8720","nameIdentifierScheme":"WEKO"},{"nameIdentifier":"1000020432461","nameIdentifierScheme":"NRID","nameIdentifierURI":"http://rns.nii.ac.jp/nr/1000020432461"}]},{"creatorNames":[{"creatorName":"Ono, Hirotaka","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"19409","nameIdentifierScheme":"WEKO"}]},{"creatorNames":[{"creatorName":"Wada, Koichi","creatorNameLang":"en"}],"nameIdentifiers":[{"nameIdentifier":"8926","nameIdentifierScheme":"WEKO"}]}]},"item_files":{"attribute_name":"ファイル情報","attribute_type":"file","attribute_value_mlt":[{"accessrole":"open_date","date":[{"dateType":"Available","dateValue":"2017-01-26"}],"displaytype":"detail","filename":"izumi_2010_TCS_1.pdf","filesize":[{"value":"206.8 kB"}],"format":"application/pdf","license_note":"Copyright c 2010 Elsevier B.V. All rights reserved.","licensetype":"license_note","mimetype":"application/pdf","url":{"label":"本文_fulltext","url":"https://nitech.repo.nii.ac.jp/record/5506/files/izumi_2010_TCS_1.pdf"},"version_id":"d3122813-7420-4cec-bcbb-4c0b48733166"}]},"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":"Approximability and inapproximability of the minimum certificate dispersal problem","item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Approximability and inapproximability of the minimum certificate dispersal problem","subitem_title_language":"en"}]},"item_type_id":"10001","owner":"91","path":["31"],"pubdate":{"attribute_name":"PubDate","attribute_value":"2013-06-25"},"publish_date":"2013-06-25","publish_status":"0","recid":"5506","relation_version_is_last":true,"title":["Approximability and inapproximability of the minimum certificate dispersal problem"],"weko_creator_id":"91","weko_shared_id":-1},"updated":"2025-03-21T05:33:48.191684+00:00"}