{"created":"2025-01-19T01:18:11.593882+00:00","metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00217713","sets":["581:10784:10788"]},"path":["10788"],"owner":"44499","recid":"217713","title":["Complexity of the Police Officer Patrol Problem "],"pubdate":{"attribute_name":"公開日","attribute_value":"2022-04-15"},"_buckets":{"deposit":"aaa424c4-abfb-4e96-b567-43454a5ee2ba"},"_deposit":{"id":"217713","pid":{"type":"depid","value":"217713","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"Complexity of the Police Officer Patrol Problem ","author_link":["564488","564487","564489","564490"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"Complexity of the Police Officer Patrol Problem "},{"subitem_title":"Complexity of the Police Officer Patrol Problem ","subitem_title_language":"en"}]},"item_keyword":{"attribute_name":"キーワード","attribute_value_mlt":[{"subitem_subject":"[一般論文] edge routing problem, vertex cover problem, mixed graph, NP-complete","subitem_subject_scheme":"Other"}]},"item_type_id":"2","publish_date":"2022-04-15","item_2_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"Maebashi Institute of Technology"},{"subitem_text_value":"Maebashi Institute of Technology"}]},"item_2_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Maebashi Institute of Technology","subitem_text_language":"en"},{"subitem_text_value":"Maebashi Institute of Technology","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"eng"}]},"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/217713/files/IPSJ-JNL6304011.pdf","label":"IPSJ-JNL6304011.pdf"},"date":[{"dateType":"Available","dateValue":"2024-04-15"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-JNL6304011.pdf","filesize":[{"value":"3.6 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"0","billingrole":"5"},{"tax":["include_tax"],"price":"0","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"8"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"69540c43-1c31-4b79-94a4-ff1d50a7923a","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2022 by the Information Processing Society of Japan"}]},"item_2_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Hiroaki, Tohyama"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Masaki, Tomisawa"}],"nameIdentifiers":[{}]}]},"item_2_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Hiroaki, Tohyama","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Masaki, Tomisawa","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_2_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN00116647","subitem_source_identifier_type":"NCID"}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_6501","resourcetype":"journal article"}]},"item_2_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"1882-7764","subitem_source_identifier_type":"ISSN"}]},"item_2_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"We introduce an edge routing decision problem called the police officer patrol problem (POPP), which is related to the vertex cover problem. A vertex cover of a graph can be regarded as the placement of police officers or fixed surveillance cameras so that each street of a neighborhood represented by the graph can be confirmed visually without moving from their position. In the edge routing problem we consider, a single police officer must confirm all the streets. The officer is allowed to move, but can confirm any street visually from an incident intersection without traversing it. In this paper, we show that the POPP on mixed graphs is NP-complete.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.30(2022) (online)\nDOI　http://dx.doi.org/10.2197/ipsjjip.30.307\n------------------------------","subitem_description_type":"Other"}]},"item_2_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"We introduce an edge routing decision problem called the police officer patrol problem (POPP), which is related to the vertex cover problem. A vertex cover of a graph can be regarded as the placement of police officers or fixed surveillance cameras so that each street of a neighborhood represented by the graph can be confirmed visually without moving from their position. In the edge routing problem we consider, a single police officer must confirm all the streets. The officer is allowed to move, but can confirm any street visually from an incident intersection without traversing it. In this paper, we show that the POPP on mixed graphs is NP-complete.\n------------------------------\nThis is a preprint of an article intended for publication Journal of\nInformation Processing(JIP). This preprint should not be cited. This\narticle should be cited as: Journal of Information Processing Vol.30(2022) (online)\nDOI　http://dx.doi.org/10.2197/ipsjjip.30.307\n------------------------------","subitem_description_type":"Other"}]},"item_2_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographic_titles":[{"bibliographic_title":"情報処理学会論文誌"}],"bibliographicIssueDates":{"bibliographicIssueDate":"2022-04-15","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"4","bibliographicVolumeNumber":"63"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":217713,"updated":"2025-01-19T15:24:17.040689+00:00","links":{}}