文献

J-GLOBAL ID：202002291364781507   整理番号：20A0593579

三角形発見のための拡張学習グラフ【JST・京大機械翻訳】

Extended Learning Graphs for Triangle Finding

著者 (3件)： Carette Titouan (Ecole Normale Superieure de Lyon, Lyon, France) ,  Lauriere Mathieu (ORFE, Princeton University, Princeton, NJ, USA) ,  Magniez Frederic (Universite de Paris, IRIF, CNRS, Paris, France)
資料名： Algorithmica  (Algorithmica)
巻： 82  号： 4  ページ： 980-1005  発行年： 2020年 
JST資料番号： T0530A  ISSN： 0178-4617  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： ドイツ (DEU)  言語： 英語 (EN)

抄録/ポイント： 著者らは,三角形のための新しい量子アルゴリズムを提示する。これは,高密度とスパースの両方の場合に対して,以前に知られている量子質問の複雑さを改善する。n頂点上の高密度グラフに対して,Le Gall[FOCS]14の以前のアルゴリズムに存在する余分な対数因子のない[数式:原文を参照]の質問複雑性を得た。[数式:原文を参照]エッジを有するスパースグラフに対して,[数式:原文を参照]の質問複雑性を得て,それは[数式:原文を参照]のとき,Le GallとNakaima[ISAAC]15によって得られたものより良かった。また,[数式:原文を参照]が次数分布の二次平均である,質問複雑性[数式:原文を参照]を有するアルゴリズムを得た。このアルゴリズムを設計し,拡張学習グラフを呼ぶ学習グラフの新しいモデルで解析した。さらに,それらを容易に結合し解析するための枠組みを示した。結果として,著者らは,MNRs量子ウォークフレームワーク[SICOMP]11に基づいて,Le Gallらの以前のアルゴリズムよりはるかに簡単なアルゴリズムと解析を得た。Copyright Springer Science+Business Media, LLC, part of Springer Nature 2019 Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： 対数 ,  *学習 ,  アルゴリズム
準シソーラス用語： 複雑性 ,  次数分布 ,  量子アルゴリズム , 【Automatic Indexing@JST】

著者キーワード (4件)： 量子問合せ複雑性 ,  量子歩行 ,  三角形の発見 ,  学習グラフ

分類 (2件)： 分子・遺伝情報処理  (JE15040B) ,  その他のオペレーションズリサーチの手法  (KA03070E)

タイトルに関連する用語 (5件)： 三角形 ,  発見 ,  拡張 ,  学習 ,  グラフ