List of Papers in 2011

Papers

1. Takehiro Ito, Naoki Sakamoto, Xiao Zhou and Takao Nishizeki
   "Minimum Cost Edge-Colorings of Trees Can be Reduced to Matchings"
   IEICE Trans. on Information and Systems, Vol. E94-D, No. 2, pp. 190-195, 2011. DOI
2. Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara and Yushi Uno
   "On the Complexity of Reconfiguration Problems"
   Theoretical Computer Science, Vol. 412, Issues 12-14, pp. 1054-1065, 2011. DOI
3. Takehiro Ito, Marcin Kamiński, Daniël Paulusma and Dimitrios M. Thilikos
   "On Disconnected Cuts and Separators"
   Discrete Applied Mathematics, Vol. 159, Issue 13, pp. 1345-1351, 2011. DOI
4. K. Uchizawa, E. Takimoto and T. Nishizeki
   "Size-Energy Tradeoffs of Unate Circuits Computing Symmetric Boolean Functions"
   Theoretical Computer Science 412(8-10), 773-782, 2011. DOI

International Conferences

1. Akira Suzuki, Kei Uchizawa and Xiao Zhou
   "Energy-efficient threshold circuits computing MOD functions"
   Proceedings of the 17th Computing: the Australasian Theory Symposium (CATS'11), CRIPT Series, CRIPT, 119, 105-110, 2011.
2. Akira Suzuki, Kei Uchizawa and Xiao Zhou
   "Energy and fan-in of threshold circuits computing Mod functions"
   Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC'11), Lect. Notes in Computer Science, Springer, 6648, pp. 154-163, 2011. DOI
3. Takehiro Ito, Kazuto Kawamura and Xiao Zhou
   "An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree"
   Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011), Lecture Notes in Computer Science, Vol. 6648, pp. 94-105, 2011. DOI
4. Takehiro Ito and Erik D. Demaine
   "Approximability of the Subset Sum Reconfiguration Problem"
   Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011), Lecture Notes in Computer Science, Vol. 6648, pp. 58-69, 2011. DOI
5. Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, and Xiao Zhou
   "On the rainbow connectivity of graphs: complexity and FPT algorithms"
   Proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON'11), Lect. Notes in Computer Science, Springer, 6842, pp. 86-97, 2011. DOI
6. K. Uchizawa and E. Takimoto
   "Lower Bounds for Linear Decision trees via An Energy Complexity Argumant"
   Proceedings of the 36th International Symposiums on Mathematical Foundations of Computer Science (MFCS), Springer LNCS 6907, pp. 568-579, 2011. DOI

国内会議

1. 青木 貴紀，鈴木 顕，内澤 啓，伊藤 健洋，周 暁
   "グラフの虹色連結判定問題を解くアルゴリズム"
   情報処理学会アルゴリズム研究会，平成23年3月7日，沖縄．
2. 川村 一斗，伊藤 健洋，周 暁
   "木のリスト辺彩色の遷移可能性"
   電子情報通信学会コンピュテーション研究会，平成23年3月9日，東京．
3. 鈴木 顕，内澤 啓，周 暁
   "剰余関数を計算するしきい値回路のエネルギー複雑度とファンイン"
   電子情報通信学会総合大会COMP学生シンポジウム，平成23年3月15日，東京．
4. Takehiro Ito and Erik D. Demaine
   "A PTAS for the Subset Sum Reconfiguration Problem"
   電子情報通信学会コンピュテーション研究会，平成23年9月6日，函館市．
5. 内澤 啓，瀧本 英二
   "エネルギー複雑度を用いた線形決定木の下界導出"
   電子情報通信学会コンピュテーション研究会，平成23年9月6日，函館市．
6. 野岡 弘幸，伊藤 健洋，周 暁
   "木，カクタスにおける点被覆の遷移可能性"
   電子情報通信学会コンピュテーション研究会，平成23年12月16日，名古屋．