Algebraic Structures and Algorithms for Matching and Matroid Problems

Nicholas J. A. Harvey
FOCS 2006
http://theory.lcs.mit.edu/~nickh/Publications/Publications.html

日本好きとして一部で有名なHarveyの論文．
グラフの最大マッチングを高速行列積計算を用いて求めるアルゴリズムが2004年にMucha and Sankowskiが提出したのはアルゴリズム業界の衝撃だったけども，そのアルゴリズムのアイディアと単純な分割統治法を組み合わせて，Mucha-Sankowskiよりもシンプルだけども同じ計算量のアルゴリズムを提案している．
代数的なアルゴリズムなので，マトロイド交わり問題にも応用できて，実際している．