{"metadata":{"_oai":{"id":"oai:ipsj.ixsq.nii.ac.jp:00217354","sets":["1164:2592:10824:10900"]},"path":["10900"],"owner":"44499","recid":"217354","title":["頂点発見問題"],"pubdate":{"attribute_name":"公開日","attribute_value":"2022-03-07"},"_buckets":{"deposit":"dd88478e-023a-4215-aa22-d624a5c059b8"},"_deposit":{"id":"217354","pid":{"type":"depid","value":"217354","revision_id":0},"owners":[44499],"status":"published","created_by":44499},"item_title":"頂点発見問題","author_link":["563040","563037","563039","563038"],"item_titles":{"attribute_name":"タイトル","attribute_value_mlt":[{"subitem_title":"頂点発見問題"},{"subitem_title":"Vertex detection problem","subitem_title_language":"en"}]},"item_type_id":"4","publish_date":"2022-03-07","item_4_text_3":{"attribute_name":"著者所属","attribute_value_mlt":[{"subitem_text_value":"東京大学大学院情報理工学系研究科"},{"subitem_text_value":"Institute of Mathematical Sciences"}]},"item_4_text_4":{"attribute_name":"著者所属(英)","attribute_value_mlt":[{"subitem_text_value":"Institute of Mathematical Sciences","subitem_text_language":"en"}]},"item_language":{"attribute_name":"言語","attribute_value_mlt":[{"subitem_language":"jpn"}]},"item_publisher":{"attribute_name":"出版者","attribute_value_mlt":[{"subitem_publisher":"情報処理学会","subitem_publisher_language":"ja"}]},"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/217354/files/IPSJ-AL22187006.pdf","label":"IPSJ-AL22187006.pdf"},"date":[{"dateType":"Available","dateValue":"2024-03-07"}],"format":"application/pdf","billing":["billing_file"],"filename":"IPSJ-AL22187006.pdf","filesize":[{"value":"1.3 MB"}],"mimetype":"application/pdf","priceinfo":[{"tax":["include_tax"],"price":"660","billingrole":"5"},{"tax":["include_tax"],"price":"330","billingrole":"6"},{"tax":["include_tax"],"price":"0","billingrole":"9"},{"tax":["include_tax"],"price":"0","billingrole":"44"}],"accessrole":"open_date","version_id":"4d1eaf85-66e9-4bb2-b2c1-adeee79de562","displaytype":"detail","licensetype":"license_note","license_note":"Copyright (c) 2022 by the Information Processing Society of Japan"}]},"item_4_creator_5":{"attribute_name":"著者名","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"小畑, 哲雅"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Venkatesh, Raman"}],"nameIdentifiers":[{}]}]},"item_4_creator_6":{"attribute_name":"著者名(英)","attribute_type":"creator","attribute_value_mlt":[{"creatorNames":[{"creatorName":"Tetto, Obata","creatorNameLang":"en"}],"nameIdentifiers":[{}]},{"creatorNames":[{"creatorName":"Venkatesh, Raman","creatorNameLang":"en"}],"nameIdentifiers":[{}]}]},"item_4_source_id_9":{"attribute_name":"書誌レコードID","attribute_value_mlt":[{"subitem_source_identifier":"AN1009593X","subitem_source_identifier_type":"NCID"}]},"item_4_textarea_12":{"attribute_name":"Notice","attribute_value_mlt":[{"subitem_textarea_value":"SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc."}]},"item_resource_type":{"attribute_name":"資源タイプ","attribute_value_mlt":[{"resourceuri":"http://purl.org/coar/resource_type/c_18gh","resourcetype":"technical report"}]},"item_4_source_id_11":{"attribute_name":"ISSN","attribute_value_mlt":[{"subitem_source_identifier":"2188-8566","subitem_source_identifier_type":"ISSN"}]},"item_4_description_7":{"attribute_name":"論文抄録","attribute_value_mlt":[{"subitem_description":"グラフの性質を特定する為に辺の情報をどの程度集める必要があるか，という問題は，古くから数多く研究されてきた [1]．これは，効率良く辺情報を得てグラフの性質を特定しようとするアルゴリズムと，グラフの情報が特定されないように適切に辺を配置する戦略との対立構造と見ることが出来る．問題の一例として有向グラフにおける出次数 k の頂点の発見問題がある．0≦k≦(n+1)/2 の場合は (n2) 回の probe クエリが必要であることが知られており [2]，これは明らかに最適値である．一方，(n+1)/2<k の場合に知られている probe 回数の下界は (n2)-(k2) 回であり [2]，上界は (n2) 回より良い値は知られていなかった．本稿では，(n+1)/2<k の場合の probe 回数の下界を (n2)-(2k-n+12) 回へと改善した．","subitem_description_type":"Other"}]},"item_4_description_8":{"attribute_name":"論文抄録(英)","attribute_value_mlt":[{"subitem_description":"It is a well known problem to research how many probes does it need to find out “some property” of a graph and it has been researched well [1]. It can be regarded as a conflict between the algorithm which probe the edges to research the property efficiently and the adversary which put and direct the edges to hide the property. The problem to find an outdegree k vertex in a directed graph is an example of it. It is known that it needs (n2) probes when 0 ≦ k ≦ (n + 1) /2 [2] and it is obviously optimal. On the other hand, it is known that it needs (n2) - (k2) probes when (n + 1) /2 < k [2] and the upper bound of the number of probes better than (n2) is not known. In this paper, we improved the lower bound to (n2) - (2k-n+12) probes when (n + 1) /2 < k.","subitem_description_type":"Other"}]},"item_4_biblio_info_10":{"attribute_name":"書誌情報","attribute_value_mlt":[{"bibliographicPageEnd":"5","bibliographic_titles":[{"bibliographic_title":"研究報告アルゴリズム（AL）"}],"bibliographicPageStart":"1","bibliographicIssueDates":{"bibliographicIssueDate":"2022-03-07","bibliographicIssueDateType":"Issued"},"bibliographicIssueNumber":"6","bibliographicVolumeNumber":"2022-AL-187"}]},"relation_version_is_last":true,"weko_creator_id":"44499"},"id":217354,"updated":"2025-01-19T15:31:46.148136+00:00","links":{},"created":"2025-01-19T01:17:51.036794+00:00"}