文献

J-GLOBAL ID：201702263376092767   整理番号：17A1774742

計数とサンプリングスパンニング木に対する応用を利用したSDDM行列の決定因子を保存するスパース化【Powered by NICT】

Determinant-Preserving Sparsification of SDDM Matrices with Applications to Counting and Sampling Spanning Trees

著者 (4件)： Durfee David ,  Peebles John ,  Peng Richard ,  Rao Anup B.
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2017  号： FOCS  ページ： 926-937  発行年： 2017年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： スペクトルスパース化ルーチンの変異体はグラフのtotalspanning樹木数,Kirchhoffs行列木定理により,SDDMマトリックスのグラフラプラシアンminor,または等価の決定基に対するisequivalentを保存できることを示した。著者らの分析は,statisticalleverageスコア/有効抵抗の間の橋渡し及びランダムgraphsby[Janson,組合せ論,確率と計算94]の分析へのこの組合せ接続を利用している。は2乗時間で,sparsifiesは行列式とdistributionofスパンニング木の両方を保存(スパースグラフはランダム物体と見なされている)方法でaboutn^(1.5)端までグラフルーチンをもたらした。このアルゴリズムはSchur補体で作動する拡張とapproximateCholesky因数分解した密グラフのための最適ほぼ計数andsamplingスパンニング木を構成するためのアルゴリズムを導いた。約n∧2/δ^2時間における一定確率でdeterminantof,SDDMマトリックス(1 +/ δ)近似を計算するアルゴリズムを与えた。これは任意の行列のcomputingdeterminantsのための汎用ルーチンよりも優れていることをグラフのための最初の一般的となっている。もW均一分布からδの全variationdistanceと分布からの重み付き無向グラフスパンニング木を約n∧2/δ^2時間で生成するアルゴリズムを与える。Copyright 2017 The Institute of Electrical and Electronics Engineers, Inc. All Rights reserved. Translated from English into Japanese by JST【Powered by NICT】

シソーラス用語： 因数分解 ,  組合せ論 ,  スペクトル ,  *スパンニング木 ,  近似法 ,  アルゴリズム ,  補体 ,  *透視図法 ,  グラフ ,  無向グラフ ,  行列式
準シソーラス用語： スコア ,  グラフラプラシアン ,  ルーチン ,  *計数 , 【Automatic Indexing@JST】

分類 (2件)： 数理物理学  (BA03000W) ,  数値計算  (JE02000J)

タイトルに関連する用語 (6件)： 計数 ,  サンプリング ,  スパンニング木 ,  応用 ,  決定因子 ,  保存