一般のグラフではChazelle (1997) のO(mα(m,n))時間アルゴリズムが知られてる中で最速． 乱数使用を許すとO(m)時間アルゴリズムがある．これはKarger-Klein-Tarjan (1995) の結果だけど，その中では与えられた全域木が最小費用全域木かどうかを判定する線形…

The Discrepancy Method: Randomness and Complexity作者: Bernard Chazelle出版社/メーカー: Cambridge University Press発売日: 2001/12/15メディア: ペーパーバック クリック: 2回この商品を含むブログ (2件) を見る偶然ソフトヒープに関する話題(?)を見…

Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series)作者: J. Flum,M. Grohe出版社/メーカー: Springer発売日: 2006/03/15メディア: ハードカバー クリック: 4回この商品を含むブログ (2件) を見るパラメータ化計算…