{"_buckets": {"deposit": "86139596-fbfc-4e53-80f6-38f88f32faa2"}, "_deposit": {"id": "41102", "owners": [], "pid": {"revision_id": 0, "type": "depid", "value": "41102"}, "status": "published"}, "_oai": {"id": "oai:tsukuba.repo.nii.ac.jp:00041102"}, "item_5_biblio_info_6": {"attribute_name": "\u66f8\u8a8c\u60c5\u5831", "attribute_value_mlt": [{"bibliographicIssueDates": {"bibliographicIssueDate": "2017-04", "bibliographicIssueDateType": "Issued"}, "bibliographicIssueNumber": "4", "bibliographicPageEnd": "1142", "bibliographicPageStart": "1128", "bibliographicVolumeNumber": "77", "bibliographic_titles": [{"bibliographic_title": "Algorithmica"}]}]}, "item_5_creator_3": {"attribute_name": "\u8457\u8005\u5225\u540d", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "\u5c0f\u6797, \u4f51\u8f14"}], "nameIdentifiers": [{"nameIdentifier": "161546", "nameIdentifierScheme": "WEKO"}]}]}, "item_5_description_4": {"attribute_name": "\u6284\u9332", "attribute_value_mlt": [{"subitem_description": "A group-labeled graph is a directed graph with each arc labeled by a group element, and the label of a path is defined as the sum of the labels of the traversed arcs. In this paper, we propose a polynomial time randomized algorithm for the problem of finding a shortest s-t path with a non-zero label in a given group-labeled graph (which we call the Shortest Non-Zero Path Problem). This problem generalizes the problem of finding a shortest path with an odd number of edges, which is known to be solvable in polynomial time by using matching algorithms. Our algorithm for the Shortest Non-Zero Path Problem is based on the ideas of Bj\u00f6rklund and Husfeldt (Proceedings of the 41st international colloquium on automata, languages and programming, part I. LNCS 8572, pp 211\u2013222, 2014). We reduce the problem to the computation of the permanent of a polynomial matrix modulo two. Furthermore, by devising an algorithm for computing the permanent of a polynomial matrix modulo 2r for any fixed integer r, we extend our result to the problem of packing internally-disjoint s-t paths.", "subitem_description_type": "Abstract"}]}, "item_5_publisher_27": {"attribute_name": "\u51fa\u7248\u8005", "attribute_value_mlt": [{"subitem_publisher": "Springer US"}]}, "item_5_relation_11": {"attribute_name": "DOI", "attribute_value_mlt": [{"subitem_relation_type_id": {"subitem_relation_type_id_text": "10.1007/s00453-016-0142-y", "subitem_relation_type_select": "DOI"}}]}, "item_5_rights_12": {"attribute_name": "\u6a29\u5229", "attribute_value_mlt": [{"subitem_rights": "\u00a9 Springer Science+Business Media New York 2016"}, {"subitem_rights": "The final publication is available at Springer via http://dx.doi.org/10.1007/s00453-016-0142-y"}]}, "item_5_select_15": {"attribute_name": "\u8457\u8005\u7248\u30d5\u30e9\u30b0", "attribute_value_mlt": [{"subitem_select_item": "author"}]}, "item_5_source_id_7": {"attribute_name": "ISSN", "attribute_value_mlt": [{"subitem_source_identifier": "0178-4617", "subitem_source_identifier_type": "ISSN"}]}, "item_5_source_id_9": {"attribute_name": "\u66f8\u8a8c\u30ec\u30b3\u30fc\u30c9ID", "attribute_value_mlt": [{"subitem_source_identifier": "AA10679010", "subitem_source_identifier_type": "NCID"}]}, "item_creator": {"attribute_name": "\u8457\u8005", "attribute_type": "creator", "attribute_value_mlt": [{"creatorNames": [{"creatorName": "Kobayashi, Yusuke"}], "nameIdentifiers": [{"nameIdentifier": "161544", "nameIdentifierScheme": "WEKO"}]}, {"creatorNames": [{"creatorName": "Toyooka, Sho"}], "nameIdentifiers": [{"nameIdentifier": "161545", "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": "2018-05-01"}], "displaytype": "detail", "download_preview_message": "", "file_order": 0, "filename": "Algorithmica_77-4.pdf", "filesize": [{"value": "151.6 kB"}], "format": "application/pdf", "future_date_message": "", "is_thumbnail": false, "licensetype": "license_free", "mimetype": "application/pdf", "size": 151600.0, "url": {"label": "Algorithmica_77-4", "url": "https://tsukuba.repo.nii.ac.jp/record/41102/files/Algorithmica_77-4.pdf"}, "version_id": "36cff134-b96e-4ffc-aca9-a5002f4f36e3"}]}, "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": "Finding a Shortest Non-zero Path in Group-Labeled Graphs via Permanent Computation", "item_titles": {"attribute_name": "\u30bf\u30a4\u30c8\u30eb", "attribute_value_mlt": [{"subitem_title": "Finding a Shortest Non-zero Path in Group-Labeled Graphs via Permanent Computation"}]}, "item_type_id": "5", "owner": "1", "path": ["152/5509", "3/62/5296/5876"], "permalink_uri": "http://hdl.handle.net/2241/00146051", "pubdate": {"attribute_name": "\u516c\u958b\u65e5", "attribute_value": "2017-05-10"}, "publish_date": "2017-05-10", "publish_status": "0", "recid": "41102", "relation": {}, "relation_version_is_last": true, "title": ["Finding a Shortest Non-zero Path in Group-Labeled Graphs via Permanent Computation"], "weko_shared_id": 5}