頂点発見問題

• Item type: SIG Technical Reports(1)
• 公開日: 2022-03-07
• タイトル: 頂点発見問題
• タイトル / 言語: en
• タイトル: Vertex detection problem
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 東京大学大学院情報理工学系研究科
• 著者所属: Institute of Mathematical Sciences
• 著者所属(英): en
• 著者所属(英): Institute of Mathematical Sciences
• 著者名: 小畑, 哲雅; Venkatesh, Raman
• 著者名(英): Tetto, Obata; Venkatesh, Raman
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: グラフの性質を特定する為に辺の情報をどの程度集める必要があるか，という問題は，古くから数多く研究されてきた [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) 回へと改善した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: 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.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN1009593X
• 書誌情報: 研究報告アルゴリズム（AL）; 巻 2022-AL-187, 号 6, p. 1-5, 発行日 2022-03-07
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 2188-8566
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会