動的接続性,流れ,および先へ適用する平衡カットのための決定性アルゴリズム【JST・京大機械翻訳】

Chuzhoy Julia; Gao Yu; Li Jason; Nanongkai Danupon; Peng Richard; Saranurak Thatchaphol

プレプリント

J-GLOBAL ID：202202219566420968 整理番号：22P0081982

動的接続性,流れ,および先へ適用する平衡カットのための決定性アルゴリズム【JST・京大機械翻訳】

A Deterministic Algorithm for Balanced Cut with Applications to Dynamic Connectivity, Flows, and Beyond

出版者サイト {{ this.onShowPLink() }} 複写サービスで全文入手
高度な検索・分析はJDreamⅢで

この文献はプレプリントです。プレプリントについてはこちらをご確認ください。

著者 (6件)： , , , , ,
資料名：
発行年： 2019年10月17日プレプリントサーバーでの情報更新日： 2020年05月03日
JST資料番号： O7000B 資料種別：プレプリント
記事区分：プレプリント発行国：アメリカ合衆国 (USA) 言語：英語 (EN)

古典的最小バランスCut問題:グラフGを与えて,部分集合を接続するエッジの数を最小にしながら,その頂点をほぼ等しい体積の2つの部分集合に分割する。この問題に対する初めての決定論的,ほぼ線形の時間近似アルゴリズムを示した。特に,n-頂点m-エッジグラフGと任意のパラメータ1≦r≦O(logn)を与えた提案アルゴリズムは,時間O(m ̄1+O(1/r)+o(1)(logm) ̄O(r ̄2))において,G上の最小バランスCutに対する(logm) ̄r ̄2-近似を計算する。特に,任意の一定εに対する時間m ̄1+O(1/π ̄*)における(logm) ̄1/ε近似および時間m ̄1+o(1)における(logm) ̄f(m)近似を,任意のゆっくり成長する関数mに対して得た。著者らは,Sparest Cutと最低コンダクタンスCut問題に対して類似の保証を持つ決定論的アルゴリズムを得た。最小バランスカット問題に対する提案アルゴリズムは,その値が与えられた目標値に近いバランスカットを返すか,あるいは高いコンダクタンスを持つGの大きな部分グラフを示すことにより,そのようなカットが存在しないことを証明できる。このアルゴリズムを用いて,動的連結性と最小スパニング森林に対する決定論的アルゴリズムを得て,n-頂点グラフ上の最悪ケース更新時間はn ̄o(1)であり,動的グラフアルゴリズムの領域における主要な未解決問題を解いた。また,本研究は,n因子におけるサブ多項式まで,既知のランダム化アルゴリズムのそれらと時間計算量がマッチする付加的問題のホストのための決定論的アルゴリズムを意味する。含意は,ラプラシアン系を解くためのほぼ線形の時間決定論的アルゴリズムを含み,無向グラフにおける最大流れを近似する。【JST・京大機械翻訳】

, , , , , , , , ,
, , , , , , 【Automatic Indexing@JST】

グラフ理論基礎

, , , ,

前のページに戻る