論文紹介
Michael I. Trofimov http://arxiv.org/abs/1004.1808グラフ同型性問題を多項式時間で解くといっていて，にわかには信じられないのだけども，謝辞を見るとこの分野の大御所が名を連ねているので，読んでみる価値はあるかもしれない．私は読んでないけども．…
Robert Ganian, Petr Hliněný, Joachim Kneis, Daniel Meister, Jan Obdržálek, Peter Rossmanith, Somnath Sikdar http://arxiv.org/abs/1004.1485グラフの木幅 (treewidth) の果たす役割はグラフ理論，グラフ・アルゴリズムの世界ではとても大きいが，その…
Balazs Szegedy http://arxiv.org/abs/1003.5588論文がスタックにたまってきたので，ちょっと吐き出します．まだ溜まってますが．これは，いわゆるSzemerediのregularity lemma (正則性補題) を解析の観点から見直して，そのスペクトル版を証明する，という…
Michael Elberfeld, Andreas Jakoby, Till Tantau ECCC TR10-062木幅を計算するためのBodlaenderのアルゴリズムと，木幅定数の性質でMonadic Second Order Logicで書けるものを判定するCourcelleのアルゴリズムの対数領域版を示している．対数領域アルゴリズ…
Authors: Johannes Brunnemann, David Rideout arXiv:1003.2348これは物理の論文だけど，有向マトロイドがでてきている．Loop Quantum Gravityというものを見ていくとそこに現れる組合せ構造が有向マトロイドになっているという話のようである．あまり読む気…
Erik D. Demaine, Martin L. Demaine, Ryuhei Uehara, Takeaki Uno, Yushi Uno http://arxiv.org/abs/1003.2851とうとう出ました！ 2人のUnoの夢であった (?) UNO論文．UNOとはもちろんあの有名なカードゲームです．
Hao Huang, Benny Sudakov ECCC TR10-026 http://eccc.hpi-web.de/report/2010/026/Alon-Saks-Seymour予想はグラフに関する予想で，グラフGの辺集合がk個の完全二部グラフに分割できれば，Gの染色数はk+1以下になる，というものである．長い間何も進展の無か…
Michael Hoffmann, Jiří Matoušek, Yoshio Okamoto, Philipp Zumstein http://arxiv.org/abs/1002.0562他の人の論文を読む時間がとれないため，自分の論文を紹介するというよくない傾向．昨日，LAシンポジウムで話した内容です．お聞きいただいた方はお分か…
Wolin A., Eoff B., Hammond T. EUROGRAPHICS 5th Annual Workshop on Sketch-Based Interfaces and Modeling (2008), pp. 33-40.手書きの図形の角を検出するアルゴリズム．こういうシンプルなものは面白いけど，もちろん角をすべて検出するような保証はない…
Radoslav Fulek, Balázs Keszegh, Filip Morić http://arxiv.org/abs/1001.3117以前紹介したWADS2009の論文の改善． 直角に辺交差するように描けるグラフ (ただし，辺は折れ線として描く) の辺の数がいくつになるか，という問題を考える． この論文では各辺…
Authors: George B. Mertzios, Ignasi Sau, Shmuel Zaks http://arxiv.org/abs/1001.3251Toleranceグラフの認識問題が多項式時間で解けるかどうかは大きな未解決問題だったけども，この論文ではそれがNP困難であることを証明している．
Sang Won Bae, Matias Korman, Yoshio Okamoto arXiv:1001.0695自分の論文を紹介するのはあまり好きじゃないのですが，たまにはやります．単純多角形の中に多角形の穴がいくつかある集合を「polygonal domain」と呼ぶのですが，その直径を計算するという話．…
Patrizio Angelini, Markus Geyer, Michael Kaufmann, Daniel Neuwirth arXiv:1001.0555木とパスが幾何同時埋め込み可能かどうかというのは，同時埋め込み可能性の分野では大きな未解決問題だったが，それを否定的に解決したとのこと．42ページもあるので読…
