文献

J-GLOBAL ID：202002288382029836   整理番号：20A1504671

e(log n)平均化時間における動的ブリッジ発見【JST・京大機械翻訳】

Dynamic bridge-finding in oe(log n) amortized time

著者 (3件)： Holm Jacob (University of Copenhagen, Denmark) ,  Rotenberg Eva (University of Copenhagen, Denmark and Technical University of Denmark, Denmark) ,  Thorup Mikkel (University of Copenhagen, Denmark)
資料名： ACM Proceedings  (ACM Proceedings)
号： SODA ’18  ページ： 35-52  発行年： 2018年 
JST資料番号： D0698C  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： グラフにおけるブリッジに関する情報を維持するための決定論的完全動的データ構造を提示した。O((log n)2)不死化時間における更新をサポートし,任意の頂点の成分におけるブリッジ,またはO(log n/log log n)最悪ケース時間で任意の2つの与えられた頂点を分離するブリッジを見つけることができた。この限界は,log log n因子までの決定論的完全動的連結性に対する限界に対して現在の最良に整合する。以前の最良の動的ブリッジ発見は,Thorup[STOC2000]によるO((log n)3)不死化時間アルゴリズムであり,Holm et al.[STOC98,JACM2001]によるO((log n)4)不死化時間アルゴリズムに関するビットトリックベースの改良であった。本アプローチは,Holmらのアルゴリズムの異なる純粋組合せ改善に基づいており,それにより,それ自身は,新しい組合せO((logn)3)不死化時間アルゴリズムを与える。それをThorupのビットトリックと結合して,著者らは,主張されたO((logn)2)不死化時間を得る。本質的に,同じ新しいトリックは,[STOC98,JACM2001]からの二接続性データ構造に適用でき,O((log n)3)への不死化更新時間を改善する。また,空間の改善も提供する。著者らは,著者らの新しいアルゴリズムおよび古いものの両方に適用する一般的トリックを記述して,線形空間を下回って,そこで,以前の最良使用O(m+nlognlog log n)を得た。その結果,静的グラフにおいてユニークな完全マッチングが存在するかどうか決定するために,改善された実行時間を得た。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  ベクトル空間 ,  データ構造 ,  連結性
準シソーラス用語： 実行時間 ,  決定論 , 【Automatic Indexing@JST】

分類 (3件)： 計算理論  (JB02000A) ,  その他のオペレーションズリサーチの手法  (KA03070E) ,  システムプログラミング一般  (JD03010Y)

タイトルに関連する用語 (2件)： ブリッジ ,  発見