2010-04-15Balazs Szegedy http://arxiv.org/abs/1003.5588 論文がスタックにたまってきたので，ちょっと吐き出します．まだ溜まってますが． これは，いわゆるSzemerediのregularity lemma (正則性補題) を解析の観点から見直して，そのスペクトル版を証明する，というもの． こういうのがすらすら読めないと本当はいけないんだけど，そういうところにまで自分は達していない． Robert Ganian, Petr Hliněný, Joachim Kneis, Daniel Meister, Jan Obdržálek, Peter Rossmanith, Somnath Sikdar http://arxiv.org/abs/1004.1485 グラフの木幅 (treewidth) の果たす役割はグラフ理論，グラフ・アルゴリズムの世界ではとても大
