抄録/ポイント：
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
カットクエリを持つ簡単なグラフのエッジ連結性を決定する複雑性を研究した。(i)O(n)カットクエリとエッジ連結性を計算する有界誤差ランダム化アルゴリズムがあり,(ii)O(√n)カットクエリとエッジ連結性を計算する有界誤差量子アルゴリズムがあることを示す。著者らは,非自明な最小カットを保存しながら,グラフのエッジをランダムに収縮する「スター収縮」と呼ばれる新しい技術を用いてこれらの結果を証明した。恒星収縮頂点では,ランダムに選ばれた頂点の小さな集合にエッジ入射をランダムに収縮させる。Ghaffari,現在,およびThorup[SODA’20]の関連する2アウト収縮技術とは対照的に,恒星収縮は頂点-関節星部分グラフを収縮し,それはカットクエリを介して効率的に実装できる。項目(i)から結合したO(n)は,連結性のより単純な問題でも知られておらず,Rubinstein,Schramm,およびWeinberg[ITCS’18]によって結合したO(nlog ̄3n)を改善した。境界は,連結性のランダム化通信複雑性がΩ(nlogn),Babai,Frankl,Simon[FOCS’86]の精力作業以来,オープンな質問である合理的な予測の下で強められる。また,境界は,単純なグラフ上のエッジ連結性を用いて除外し,対称サブモジュール関数を最小化するための超線形ランダム化クエリー下限を証明した。項目(ii)は,ランダム化した複雑性でほぼ二次的な分離を与え,Lee,Santha,Zhang[SODA’21]の未解決の問題を扱う。また,このアルゴリズムは,隣接行列に対する ̄O(√n)行列ベクトル乗算クエリーとして見ることができる。最後に,頂点到着設定におけるエッジ連結性を計算するためのワンパス半ストリーミングアルゴリズムを設計することによって,カットクエリ設定の外で恒星収縮の使用を実証した。このコントラストは,2つのパスが必要とされるエッジ到着設定と対照的である。【JST・京大機械翻訳】
