Bidimensionality and EPTAS

Fedor V. Fomin, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh
http://arxiv.org/abs/1005.5449

広いクラスのグラフ上の広いクラスの問題に対してEffcient polynomial-time approximation scheme (EPTAS) を与えている．広いクラスのグラフというのは，あるグラフをマイナーとして含まないグラフで，広いクラスの問題とはbidimensionalな問題．以前のDemaineらの結果の精緻化．