抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
任意の部分グラフをmエッジでグラフGから均一にサンプリングするための簡単なサブ線形時間アルゴリズムを示し,このアルゴリズムは次のタイプのクエリを実行することによりアクセスした。(1)度合クエリ,(2)隣接クエリ,(3)ペアクエリ,(4)エッジサンプリングクエリ。提案アルゴリズムのクエリ複雑性と実行時間は,それぞれ,O(min{m,frac{m ̄{ρ(H)}>H}とO(frac{m ̄{ρ(H)}}{#H})であり,ρ(H)はHと#Hの分数エッジカバーであり,GにおけるHのコピーの数である。r頂点,すなわち,H=K_rの任意のクリークに対して,このアルゴリズムは,Hの全てのコピーのセットにΩ(1)全確率質量を持つ任意の分布からHを,Ω(min{m,frac{m ̄{ρ(H) ̄}}{#H.(cr) ̄r→∞)クエリーを実行しなければならない任意のアルゴリズムとして,ほとんど最適である。AssadiによるサブグラフHの数に対する(1±ε)近似アルゴリズムの質問と時間複雑性,KapralovとKhanna[ITCS 2018],およびEdenとRosenbaum[APPROX 2018]による下限は,この質問モデルにおいて,正確に均一なサンプリングとランダム化近似計数の質問と時間複雑性が互いに多対数的因子内にあるという意味で,この質問モデルにおいては,クリークが正確に均一サンプリングするのに「等価である」ことを,我々の結果は示す。。”著者らの結果は,この質問モデルにおいて,クリークが正確に均一サンプリングするという意味で,この質問モデルにおいて,クリークが正確に均一サンプリングするという意味において,この質問モデルにおいて,この質問と時間複雑性は,正確に一様にサンプリングするという意味で,この質問モデルにおいて,この質問と時間の複雑性は,正確に均一サンプリングのクリークに「等価である」ことを暗示した。これは,Jerrum,ValiantおよびVaziani[TCS 1986]による多項式時間領域での自己還元性問題に対して,近似計数とほぼ均一サンプリングの間の類似の関係と興味深い対照的である。【JST・京大機械翻訳】
