Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors - todo314 @ ウィキ

Algebraic Algorithms for b-Matching, Shortest Undirected Paths, and f-Factors

• Harold N. Gabow, Pitor Sankowski
• In FOCS 2013

• b-machingとf-factorのO(φ^ω)-time Algebraic Algorithm
• Algebraic Algorithm
  • 行列演算で組み合わせ問題を乱択な感じで解く
  • 例: 二部グラフマッチング、マトロイド交差
• 最大マッチング
  • 一般グラフのマッチング（Tutteの定理）を使ってみる
  • Naiveなalgo. O(n^{ω+2})
    • G\ijがmax-matchingを持つか調べつつ辺を消していく
  • ちょっと速いO(n^4)
    • GのAとG\ijのA'は差が小さい
    • det(A)->det(A')の計算はn^2でOK
  • かなり速いHarveyO(n^ω)
    • 上の更新を遅延評価みたいにする
    • 一般的に使える枠組みでこの論文もこれに頼る
• f-factor
  • f:V→Z+
  • M⊆Eがf-factor⇔d_M(v)=f(v)
    • Mだけ残すと全部次数がf(v)
• b-matching
  • b:V→Z+
  • x∈Z+^Eがb-matching⇔x(δ(v))=b(v)
    • δ: vに接続する辺集合
• Harveyのに適用出来るように行列をうまいこと作ったのがContribution

FOCS

2013-11-03 02:27:54 (Sun)