研究者詳細

顔写真

イトウ　タケヒロ
伊藤　健洋
Takehiro Ito
所属
大学院情報科学研究科　システム情報科学専攻　生体システム情報学講座（情報システム評価学分野）
職名
教授
学位

  • 博士（情報科学） （東北大学）

e-Rad 研究者番号
40431548

経歴 9

  • 2020年5月 ～ 継続中
    東北大学 大学院情報科学研究科　教授

  • 2020年4月 ～ 2024年3月
    東北大学

  • 2012年1月 ～ 2020年4月
    東北大学 大学院情報科学研究科　准教授

  • 2007年4月 ～ 2011年12月
    東北大学 大学院情報科学研究科　助教

  • 2008年10月 ～ 2009年3月
    ブリュッセル自由大学　客員研究員

  • 2008年3月 ～ 2008年6月
    マギル大学　客員研究員

  • 2006年4月 ～ 2007年3月
    東北大学 大学院情報科学研究科　助手

  • 2003年4月 ～ 2006年3月
    日本学術振興会　特別研究員（DC1）

  • 2005年6月 ～ 2005年10月
    マサチューセッツ工科大学　訪問学生

︎全件表示 ︎最初の5件までを表示

学歴 3

  • 東北大学　大学院情報科学研究科　システム情報科学専攻

    2003年4月 ～ 2006年3月

  • 東北大学　大学院情報科学研究科　システム情報科学専攻

    2001年10月 ～ 2003年3月

  • 東北大学　工学部　情報工学科

    1998年4月 ～ 2001年9月

委員歴 9

  • Asian Association for Algorithms and Computation　Board Member

    2025年5月 ～ 継続中

  • LAシンポジウム　2025年度代表

    2025年4月 ～ 継続中

  • European Association for Theoretical Computer Science, Japan Chapter　副会長

    2019年2月 ～ 継続中

  • 文部科学省 科学技術・学術政策研究所 科学技術予測・政策基盤調査研究センター　専門調査員

    2016年4月 ～ 継続中

  • 情報処理学会アルゴリズム研究運営委員会　運営委員

    2018年4月 ～ 2022年4月

  • European Association for Theoretical Computer Science, Japan Chapter　幹事

    2014年1月 ～ 2019年1月

  • 電子情報通信学会 コンピュテーション研究専門委員会　専門委員

    2012年6月 ～ 2018年5月

  • 文部科学省 科学技術・学術政策研究所 科学技術動向研究センター　専門調査員

    2014年4月 ～ 2016年3月

  • 電子情報通信学会 コンピュテーション研究専門委員会　幹事

    2010年5月 ～ 2012年5月

︎全件表示 ︎最初の5件までを表示

所属学協会 2

  • 電子情報通信学会

  • 情報処理学会

研究キーワード 2

  • 組合せ遷移

  • グラフアルゴリズム

研究分野 1

  • 情報通信 / 情報学基礎論 /

受賞 16

  1. FIT2020船井ベストペーパー賞

    2021年8月　公益財団法人 船井情報科学振興財団

  2. 山下記念研究賞

    2020年3月　情報処理学会

  3. 研究奨励賞

    2018年11月　石田實記念財団

  4. 第17回（平成29年度）船井学術賞

    2018年4月　船井情報科学振興財団

  5. 平成30年度科学技術分野の文部科学大臣表彰 若手科学者賞

    2018年4月　文部科学省

  6. 平成25年度（第3回） RIEC Award 東北大学研究者賞

    2013年11月21日　電気通信工学振興会

  7. 第8回船井情報科学奨励賞

    2009年4月18日　船井情報科学振興財団

  8. Best Paper Award of ISAAC 2008

    2008年12月16日　The 19th International Symposium on Algorithms and Computation

  9. McGill-Japan Visiting Scholar Awards 2008

    2007年11月　McGill University

  10. 第2回野口研究奨励賞

    2007年5月9日　情報処理学会東北支部

  11. 情報科学研究科長賞

    2006年3月　東北大学大学院情報科学研究科

  12. 総長賞

    2006年3月　東北大学

  13. 青葉工学振興会 第11回研究奨励賞

    2005年12月14日　青葉工学振興会

  14. 2003年度 C&C若手優秀論文賞

    2004年1月28日　C&C振興財団

  15. 第18回テレコムシステム技術学生賞

    2003年3月　電気通信普及財団

  16. 2001年度 LA発表論文賞

    2002年2月　LAシンポジウム

︎全件表示 ︎最初の5件までを表示

論文 152

  1. Independent set reconfiguration under bounded-hop token jumping 招待有り 査読有り

    Hiroki Hatano, Naoki Kitamura, Taisuke Izumi, Takehiro Ito, Toshimitsu Masuzawa

    Theoretical Computer Science　1062　115651　2026年2月2日

    DOI： 10.1016/j.tcs.2025.115651 　

  2. Reconfiguration of time-respecting arborescences 査読有り

    Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira Suzuki

    Algorithmica　88　(1)　15　2026年2月

    DOI： 10.1007/s00453-025-01365-1 　

  3. Minimum sum coloring with bundles in trees and bipartite graphs 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    Proceedings of the 36th International Symposium on Algorithms and Computation (ISAAC 2025)　359　40:1-40:14　2025年11月27日

    DOI： 10.4230/LIPIcs.ISAAC.2025.40 　

  4. Multi-objective combinatorial reconfiguration considering cost and length by answer set programming: Algorithms, encodings, and empirical analysis 国際共著 査読有り

    Kazuki Takada, Mutsunori Banbara, Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Torsten Schaub, Ryuhei Uehara

    Proceedings of the 28th European Conference on Artificial Intelligence (ECAI 2025)　413　1575-1582　2025年10月21日

    出版者・発行元： IOS Press

    DOI： 10.3233/faia250982 　

    ISSN：0922-6389

    eISSN：1879-8314

    詳細を見る 詳細を閉じる

    We introduce the Multi-Objective Combinatorial Reconfiguration Optimization Problem (MO-CROP), and propose an Answer Set Programming (ASP) based approach for its solution. MO-CROP involves finding the Pareto-optimal sequences (or Pareto front) of adjacent feasible solutions between two given feasible solutions of a combinatorial problem, considering both cost and length. Our algorithm is compactly implemented through multi-shot ASP solving, and its implementing solver optirecon provides an effective tool for solving MO-CROP. As a concrete example of MO-CROP, we present an ASP encoding for solving the multi-objective independent set reconfiguration optimization problem. Experimental results on the benchmark set from the recent CoRe Challenge demonstrate our approach’s ability to capture diverse optimal sequences that reveal trade-offs between cost and length, a capability often lacking in traditional combinatorial reconfiguration methods.

  5. Minimum sum coloring with bundles in trees and bipartite graphs

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    CoRR　abs/2509.15080　2025年9月18日

    DOI： 10.48550/arXiv.2509.15080 　

  6. Algorithmic theory of qubit routing in the linear nearest neighbor architectures 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    ACM Transactions on Quantum Computing　6　(3)　19　2025年5月30日

    出版者・発行元： Association for Computing Machinery (ACM)

    DOI： 10.1145/3722119 　

    ISSN：2643-6809

    eISSN：2643-6817

  7. Reconfiguration of colorings in triangulations of the sphere 査読有り

    Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

    Journal of Computational Geometry　16　(1)　253-294　2025年4月10日

    DOI： 10.20382/jocg.v16i1a8 　

  8. Reforming an envy-free matching 査読有り

    Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

    Algorithmica　87　(4)　594-620　2025年4月

    DOI： 10.1007/s00453-025-01294-z 　

  9. Rerouting planar curves and disjoint paths 査読有り

    Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

    ACM Transactions on Algorithms　21　(2)　20　2025年3月13日

    出版者・発行元： Association for Computing Machinery (ACM)

    DOI： 10.1145/3715694 　

    ISSN：1549-6325

    eISSN：1549-6333

  10. Independent set reconfiguration under bounded-hop token jumping 査読有り

    Hiroki Hatano, Naoki Kitamura, Taisuke Izumi, Takehiro Ito, Toshimitsu Masuzawa

    Proceedings of the 19th International Conference and Workshops on Algorithms and Computation (WALCOM 2025)　15411　215-228　2025年2月

    DOI： 10.1007/978-981-96-2845-2_14 　

  11. 停電残量最小化を目的とした配電系統構成の多角的評価 査読有り

    杉村 修平, 金子 曜久, 林 泰弘, 野崎 哲平, 鈴木 顕, 伊藤 健洋, 田邊 隆之

    電気学会論文誌Ｂ　144　(12)　640-649　2024年12月1日

    出版者・発行元：

    DOI： 10.1541/ieejpes.144.640 　

    ISSN：0385-4213

    eISSN：1348-8147

  12. Algorithmic meta-theorems for combinatorial reconfiguration revisited 査読有り

    Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi

    Algorithmica　86　(11)　3395-3424　2024年11月

    DOI： 10.1007/s00453-024-01261-0 　

  13. Reconfiguration of vertex-disjoint shortest paths on graphs 査読有り

    Rin Saito, Hiroshi Eto, Takehiro Ito, Ryuhei Uehara

    Journal of Graph Algorithms and Applications　28　(3)　87-101　2024年9月

    DOI： 10.7155/jgaa.v28i3.2973 　

  14. Independent set reconfiguration under bounded-hop token

    Hiroki Hatano, Naoki Kitamura, Taisuke Izumi, Takehiro Ito, Toshimitsu Masuzawa

    CoRR　abs/2407.11768　2024年7月

    DOI： 10.48550/arXiv.2407.11768 　

  15. Scalable hard instances for independent set reconfiguration 査読有り

    Takehide Soh, Takumu Watanabe, Jun Kawahara, Akira Suzuki, Takehiro Ito

    Proceedings of the 22nd International Symposium on Experimental Algorithms (SEA 2024)　301　26:1-26:15　2024年7月

    出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    DOI： 10.4230/LIPIcs.SEA.2024.26 　

  16. CoRe challenge 2022/2023: Empirical evaluations for independent set reconfiguration problems (Extended abstract) 査読有り

    Takehide Soh, Tomoya Tanjo, Yoshio Okamoto, Takehiro Ito

    Proceedings of the 17th International Symposium on Combinatorial Search (SoCS 2024)　17　285-286　2024年6月

    出版者・発行元： AAAI Press

    DOI： 10.1609/socs.v17i1.31583 　

  17. Solving reconfiguration problems of first-order expressible properties of graph vertices with Boolean satisfiability 査読有り

    Takahisa Toda, Takehiro Ito, Jun Kawahara, Takehide Soh, Akira Suzuki, Junichi Teruyama

    Proceedings of the 35th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2023)　294-302　2023年12月

    出版者・発行元： IEEE

    DOI： 10.1109/ICTAI59109.2023.00050 　

  18. On reachable assignments under dichotomous preferences 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

    Theoretical Computer Science　979　114196　2023年11月

    DOI： 10.1016/j.tcs.2023.114196 　

  19. Sorting balls and water: Equivalence and computational complexity 査読有り

    Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka

    Theoretical Computer Science　978　114158　2023年11月

    DOI： 10.1016/j.tcs.2023.114158 　

  20. Happy set problem on subclasses of co-comparability graphs 査読有り

    Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura

    Algorithmica　85　(11)　3327-3347　2023年11月

    DOI： 10.1007/s00453-022-01081-0 　

  21. Reconfiguration of spanning trees with degree constraints or diameter constraints 査読有り

    Nicolas Bousque, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, Kunihiro Wasa

    Algorithmica　85　(9)　2779-2816　2023年9月

    DOI： 10.1007/s00453-023-01117-z 　

  22. Algorithmic theory of qubit routing 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023)　14079　533-546　2023年7月

    DOI： 10.1007/978-3-031-38906-1_35 　

  23. Reconfiguration of time-respecting arborescences 査読有り

    Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira Suzuki

    Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023)　14079　521-532　2023年7月

    DOI： 10.1007/978-3-031-38906-1_34 　

  24. Hardness of finding combinatorial shortest paths on graph associahedra 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto

    Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023)　261　82:1-82:17　2023年7月

    DOI： 10.4230/LIPIcs.ICALP.2023.82 　

  25. Rerouting planar curves and disjoint paths 査読有り

    Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

    Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023)　81:1-81:19　2023年7月

    DOI： 10.4230/LIPIcs.ICALP.2023.81 　

  26. Reconfiguration of cliques in a graph 査読有り

    Takehiro Ito, Hirotaka Ono, Yota Otachi

    Discrete Applied Mathematics　333　43-58　2023年7月

    DOI： 10.1016/j.dam.2023.01.026 　

  27. Reconfiguration of colorings in triangulations of the sphere 査読有り

    Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

    Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023)　258　43:1-43:16　2023年6月

    DOI： 10.4230/LIPIcs.SoCG.2023.43 　

  28. ZDD-based algorithmic framework for solving shortest reconfiguration problems 査読有り

    Takehiro Ito, Jun Kawahara, Yu Nakahata, Takehide Soh, Akira Suzuki, Junichi Teruyama, Takahisa Toda

    Proceedings of the 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2023)　13884　167-183　2023年5月

    DOI： 10.1007/978-3-031-33271-5_12 　

  29. Fixed-parameter algorithms for graph constraint logic 査読有り

    Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, Akira Suzuki

    Theoretical Computer Science　959　113863　2023年5月

    DOI： 10.1016/j.tcs.2023.113863 　

  30. Reconfiguration of vertex-disjoint shortest paths on graphs 査読有り

    Rin Saito, Hiroshi Eto, Takehiro Ito, Ryuhei Uehara

    Proceedings of the 17th International Conference and Workshops on Algorithms and Computation (WALCOM 2023)　13973　191-201　2023年3月

    DOI： 10.1007/978-3-031-27051-2_17 　

  31. Reconfiguring (non-spanning) arborescences 査読有り

    Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa

    Theoretical Computer Science　943　131-141　2023年1月

    DOI： 10.1016/j.tcs.2022.12.007 　

  32. Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams 査読有り

    Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

    ACM Transactions on Algorithms　19　(1)　6　2023年1月

    DOI： 10.1145/3561302 　

  33. Approximability of the distance independent set problem on regular graphs and planar graphs 査読有り

    Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences　105-A　(9)　1211-1222　2022年9月

    DOI： 10.1587/transfun.2021dmp0017 　

  34. Happy set problem on subclasses of co-comparability graphs 査読有り

    Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura

    WALCOM: Algorithms and Computation - 16th International Conference and Workshops (WALCOM)　149-160　2022年

    出版者・発行元： Springer

    DOI： 10.1007/978-3-030-96731-4_13 　

  35. Reconfiguration of regular induced subgraphs 査読有り

    Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, Kunihiro Wasa

    WALCOM: Algorithms and Computation - 16th International Conference and Workshops (WALCOM)　35-46　2022年

    出版者・発行元： Springer

    DOI： 10.1007/978-3-030-96731-4_4 　

  36. Invitation to combinatorial reconfiguration 招待有り

    Takehiro Ito

    WALCOM: Algorithms and Computation - 16th International Conference and Workshops (WALCOM)　26-31　2022年

    出版者・発行元： Springer

    DOI： 10.1007/978-3-030-96731-4_3 　

  37. Reconfiguration of spanning trees with degree constraint or diameter constraint 査読有り

    Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, Kunihiro Wasa

    39th International Symposium on Theoretical Aspects of Computer Science (STACS)　15:1-15:21　2022年

    出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    DOI： 10.4230/LIPIcs.STACS.2022.15 　

  38. Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams 査読有り

    Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

    Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA)　1342-1355　2022年

    出版者・発行元： SIAM

    DOI： 10.1137/1.9781611977073.56 　

  39. Sorting balls and water: Equivalence and computational complexity 査読有り

    Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka

    11th International Conference on Fun with Algorithms (FUN)　16:1-16:17　2022年

    出版者・発行元： Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    DOI： 10.4230/LIPIcs.FUN.2022.16 　

  40. Invitation to combinatorial reconfiguration (Invited Talk) 招待有り

    Takehiro Ito

    CPM　1-1　2022年

    DOI： 10.4230/LIPIcs.CPM.2022.1 　

  41. Reforming an envy-free matching 査読有り

    Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

    AAAI　5084-5091　2022年

    DOI： 10.1609/aaai.v36i5.20441 　

  42. Shortest reconfiguration of perfect matchings via alternating cycles 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    SIAM Journal on Discrete Mathematics　36　(2)　1102-1123　2022年

    DOI： 10.1137/20m1364370 　

  43. A parameterized view to the robust recoverable base problem of matroids under structural uncertainty 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    Operations Research Letters　50　(3)　370-375　2022年

    DOI： 10.1016/j.orl.2022.05.001 　

  44. Incremental optimization of independent sets under the reconfiguration framework 査読有り

    Takehiro Ito, Haruka Mizuta, Naomi Nishimura, Akira Suzuki

    Journal of Combinatorial Optimization　43　(5)　1264-1279　2022年

    DOI： 10.1007/s10878-020-00630-z 　

  45. Reconfiguring directed trees in a digraph 査読有り

    Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa

    Computing and Combinatorics - 27th International Conference (COCOON)　343-354　2021年

    出版者・発行元： Springer

    DOI： 10.1007/978-3-030-89543-3_29 　

  46. Algorithms for gerrymandering over graphs 査読有り

    Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    Theoretical Computer Science　868　30-45　2021年

    DOI： 10.1016/j.tcs.2021.03.037 　

  47. Approximability of the independent feedback vertex set problem for bipartite graphs 査読有り

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    Theoretical Computer Science　849　227-236　2021年

    DOI： 10.1016/j.tcs.2020.10.026 　

  48. Parameterized complexity of independent set reconfiguration problems 査読有り

    Takehiro Ito, Marcin Kamiński, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, Katsuhisa Yamanaka

    Discrete Applied Mathematics　283　336-345　2020年9月

    出版者・発行元：

    DOI： 10.1016/j.dam.2020.01.022 　

    ISSN：0166-218X

  49. Reconfiguring spanning and induced subgraphs 査読有り

    Tesshu Hanaka, Takehiro Ito, Haruka Mizuta, Benjamin Moore, Naomi Nishimura, Vijay Subramanya, Akira Suzuki, Krishna Vaidyanathan

    Theoretical Computer Science　806　553-566　2020年2月

    DOI： 10.1016/j.tcs.2019.09.018 　

  50. Approximability of the independent feedback vertex set problem for bipartite graphs 査読有り

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    Proceedings of the 14th International Conference and Workshop on Algorithms and Computation (WALCOM 2020), Lecture Notes in Computer Science　12049　286-295　2020年

    DOI： 10.1007/978-3-030-39881-1_24 　

  51. Shortest reconfiguration of colorings under Kempe changes 査読有り

    Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, Kunihiro Wasa

    Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Leibniz International Proceedings in Informatics　154　35:1-35:14　2020年

    DOI： 10.4230/LIPIcs.STACS.2020.35 　

  52. Reconfiguration of colorable sets in classes of perfect graphs 査読有り

    Takehiro Ito, Yota Otachi

    Theoretical Computer Science　772　111-122　2019年6月

    DOI： 10.1016/j.tcs.2018.11.024 　

  53. The coloring reconfiguration problem on specific graph classes 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    IEICE Trans. on Information and Systems　102-D　(3)　423-429　2019年3月

    DOI： 10.1587/transinf.2018FCP0005 　

  54. Reconfiguration of maximum-weight b-matchings in a graph 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    Journal of Combinatorial Optimization　37　(2)　454-464　2019年2月

    DOI： 10.1007/s10878-018-0289-3 　

  55. Shortest reconfiguration of matchings 査読有り

    Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, Moritz Mühlenthaler

    Proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2019)　11789　162-174　2019年

    DOI： 10.1007/978-3-030-30786-8_13 　

  56. The perfect matching reconfiguration problem 査読有り

    Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, Kunihiro Wasa

    Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)　138　80:1-80:14　2019年

    DOI： 10.4230/LIPIcs.MFCS.2019.80 　

  57. Reconfiguration of minimum Steiner trees via vertex exchanges 査読有り

    Haruka Mizuta, Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)　138　79:1-79:11　2019年

    DOI： 10.4230/LIPIcs.MFCS.2019.79 　

  58. Shortest reconfiguration of perfect matchings via alternating cycles 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019), Leibniz International Proceedings in Informatics　144　61:1-61:15　2019年

    DOI： 10.4230/LIPIcs.ESA.2019.61 　

  59. Incremental optimization of independent sets under the reconfiguration framework 査読有り

    Takehiro Ito, Haruka Mizuta, Naomi Nishimura, Akira Suzuki

    Proceedings of the 25th International Computing and Combinatorics Conference (COCOON 2019)　11653　313-324　2019年

    DOI： 10.1007/978-3-030-26176-4_26 　

  60. Diameter of colorings under Kempe changes 査読有り

    Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, Kunihiro Wasa

    Proceedings of the 25th International Computing and Combinatorics Conference (COCOON 2019)　11653　52-64　2019年

    DOI： 10.1007/978-3-030-26176-4_5 　

  61. Algorithms for gerrymandering over graphs 査読有り

    Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019)　1413-1421　2019年

  62. Minimum-cost b-edge dominating sets on trees 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    Algorithmica　81　(1)　343-366　2019年1月

    DOI： 10.1007/s00453-018-0448-z 　

  63. Reconfiguration of colorable sets in classes of perfect graphs 査読有り

    Takehiro Ito, Yota Otachi

    Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)　101　27:1-27:13　2018年

  64. Algorithms for coloring reconfiguration under recolorability constraints. 査読有り

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018)　123　37:1-37:13　2018年

    DOI： 10.4230/LIPIcs.ISAAC.2018.37 　

  65. The complexity of (list) edge-coloring reconfiguration problem 査読有り

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    IEICE Transactions　101-A　(1)　232-238　2018年

    DOI： 10.1587/transfun.E101.A.232 　

  66. Parameterized complexity of the list coloring reconfiguration problem with graph parameters 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    Theoretical Computer Science　739　65-79　2018年

    DOI： 10.1016/j.tcs.2018.05.005 　

  67. Reconfiguring spanning and induced subgraphs 査読有り

    Tesshu Hanaka, Takehiro Ito, Haruka Mizuta, Benjamin Moore, Naomi Nishimura, Vijay Subramanya, Akira Suzuki, Krishna Vaidyanathan

    Computing and Combinatorics - 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018, Proceedings　428-440　2018年

    DOI： 10.1007/978-3-319-94776-1_36 　

  68. Complexity of tiling a polygon with trominoes or bars 査読有り

    Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, Ryuhei Uehara

    Discrete & Computational Geometry　58　(3)　686-704　2017年

    DOI： 10.1007/s00454-017-9884-9 　

  69. Reconfiguration of Steiner trees in an unweighted graph 査読有り

    Haruka Mizuta, Takehiro Ito, Xiao Zhou

    IEICE Transactions　100-A　(7)　1532-1540　2017年

    DOI： 10.1587/transfun.E100.A.1532 　

  70. Efficient stabilization of cooperative matching games 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    Theoretical Computer Science　677　69-82　2017年

    DOI： 10.1016/j.tcs.2017.03.020 　

  71. Tight approximability of the server allocation problem for real-time applications 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto, Taichi Shiitada

    Algorithmic Aspects of Cloud Computing - Third International Workshop, ALGOCLOUD 2017, Vienna, Austria, September 5, 2017, Revised Selected Papers　41-55　2017年

    DOI： 10.1007/978-3-319-74875-7_4 　

  72. The coloring reconfiguration problem on specific graph classes 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I　152-162　2017年

    DOI： 10.1007/978-3-319-71150-8_15 　

  73. Reconfiguration of maximum-weight b-matchings in a graph 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    Computing and Combinatorics - 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings　287-296　2017年

    DOI： 10.1007/978-3-319-62389-4_24 　

  74. Complexity of the multi-service center problem 査読有り

    Takehiro Ito, Naonori Kakimura, Yusuke Kobayashi

    28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand　48:1-48:12　2017年

    DOI： 10.4230/LIPIcs.ISAAC.2017.48 　

  75. Complexity of coloring reconfiguration under recolorability constraints 査読有り

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand　62:1-62:12　2017年

    DOI： 10.4230/LIPIcs.ISAAC.2017.62 　

  76. Parameterized complexity of the list coloring reconfiguration problem with graph parameters 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark　51:1-51:13　2017年

    DOI： 10.4230/LIPIcs.MFCS.2017.51 　

  77. Approximation algorithm for the distance-3 independent set problem on cubic graphs 査読有り

    Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano

    WALCOM: Algorithms and Computation, 11th International Conference and Workshops, WALCOM 2017, Hsinchu, Taiwan, March 29-31, 2017, Proceedings.　228-240　2017年

    DOI： 10.1007/978-3-319-53925-6_18 　

  78. The complexity of (list) edge-coloring reconfiguration problem 査読有り

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    WALCOM: Algorithms and Computation, 11th International Conference and Workshops, WALCOM 2017, Hsinchu, Taiwan, March 29-31, 2017, Proceedings.　347-358　2017年

    DOI： 10.1007/978-3-319-53925-6_27 　

  79. A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares 査読有り

    Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    Computational Geometry: Theory and Applications　51　25-39　2016年

    DOI： 10.1016/j.comgeo.2015.10.004 　

  80. Reconfiguration of vertex covers in a graph 査読有り

    Takehiro Ito, Hiroyuki Nooka, Xiao Zhou

    IEICE Transactions　99-D　(3)　598-606　2016年

    DOI： 10.1587/transinf.2015FCP0010 　

  81. The minimum vulnerability problem on specific graph classes 査読有り

    Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou

    Journal of Combinatorial Optimization　32　(4)　1288-1304　2016年

    DOI： 10.1007/s10878-015-9950-2 　

  82. The complexity of dominating set reconfiguration 査読有り

    Arash Haddadan, Takehiro Ito, Amer E. Mouawad, Naomi Nishimura, Hirotaka Ono, Akira Suzuki, Youcef Tebbal

    Theoretical Computer Science　651　37-49　2016年

    DOI： 10.1016/j.tcs.2016.08.016 　

  83. Efficient stabilization of cooperative matching games 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, Singapore, May 9-13, 2016　41-49　2016年

  84. Approximability of the distance independent set problem on regular graphs and planar graphs 査読有り

    Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano

    Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016, Proceedings　270-284　2016年

    DOI： 10.1007/978-3-319-48749-6_20 　

  85. Reconfiguration of Steiner trees in an unweighted graph 査読有り

    Haruka Mizuta, Takehiro Ito, Xiao Zhou

    Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings　163-175　2016年

    DOI： 10.1007/978-3-319-44543-4_13 　

  86. Experimental evaluations of dynamic algorithm for maintaining shortest-paths trees on real-world networks 査読有り

    Takashi Hasegawa, Takehiro Ito, Akira Suzuki, Xiao Zhou

    Interdisciplinary Information Sciences　21　(1)　25-35　2015年

    DOI： 10.4036/iis.2015.25 　

  87. The list coloring reconfiguration problem for bounded pathwidth graphs 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    IEICE Transactions　98-A　(6)　1168-1178　2015年

    DOI： 10.1587/transfun.E98.A.1168 　

  88. Algorithms for the independent feedback vertex set problem 査読有り

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    IEICE Transactions　98-A　(6)　1179-1188　2015年

    DOI： 10.1587/transfun.E98.A.1179 　

  89. Swapping labeled tokens on graphs 査読有り

    Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, Takeaki Uno

    Theoretical Computer Science　586　81-94　2015年

    DOI： 10.1016/j.tcs.2015.01.052 　

  90. Linear-time algorithm for sliding tokens on trees 査読有り

    Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada

    Theoretical Computer Science　600　132-142　2015年

    DOI： 10.1016/j.tcs.2015.07.037 　

  91. Reconfiguration of cliques in a graph 査読有り

    Takehiro Ito, Hirotaka Ono, Yota Otachi

    Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, Proceedings　212-223　2015年

    DOI： 10.1007/978-3-319-17142-5_19 　

  92. The complexity of dominating set reconfiguration 査読有り

    Arash Haddadan, Takehiro Ito, Amer E. Mouawad, Naomi Nishimura, Hirotaka Ono, Akira Suzuki, Youcef Tebbal

    Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings　398-409　2015年

    DOI： 10.1007/978-3-319-21840-3_33 　

  93. Competitive diffusion on weighted graphs 査読有り

    Takehiro Ito, Yota Otachi, Toshiki Saitoh, Hisayuki Satoh, Akira Suzuki, Kei Uchizawa, Ryuhei Uehara, Katsuhisa Yamanaka, Xiao Zhou

    Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings　422-433　2015年

    DOI： 10.1007/978-3-319-21840-3_35 　

  94. On the minimum caterpillar problem in digraphs 査読有り

    Taku Okada, Akira Suzuki, Takehiro Ito, Xiao Zhou

    IEICE Transactions　97-A　(3)　848-857　2014年

    DOI： 10.1587/transfun.E97.A.848 　

  95. Approximability of the subset sum reconfiguration problem 査読有り

    Takehiro Ito, Erik D. Demaine

    Journal of Combinatorial Optimization　28　(3)　639-654　2014年

    DOI： 10.1007/s10878-012-9562-z 　

  96. A 4.31-approximation for the geometric unique coverage problem on unit disks 査読有り

    Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    Theoretical Computer Science　544　14-31　2014年

    DOI： 10.1016/j.tcs.2014.04.014 　

  97. Reconfiguration of list L(2,1)-labelings in a graph 査読有り

    Takehiro Ito, Kazuto Kawamura, Hirotaka Ono, Xiao Zhou

    Theoretical Computer Science　544　84-97　2014年

    DOI： 10.1016/j.tcs.2014.04.011 　

  98. Complexity of finding maximum regular induced subgraphs with prescribed degree 査読有り

    Yuichi Asahiro, Hiroshi Eto, Takehiro Ito, Eiji Miyano

    Theoretical Computer Science　550　21-35　2014年

    DOI： 10.1016/j.tcs.2014.07.008 　

  99. Generalized rainbow connectivity of graphs 査読有り

    Kei Uchizawa, Takanori Aoki, Takehiro Ito, Xiao Zhou

    Theoretical Computer Science　555　35-42　2014年

    DOI： 10.1016/j.tcs.2014.01.007 　

  100. Base-object location problems for base-monotone regions 査読有り

    Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno

    Theoretical Computer Science　555　71-84　2014年

    DOI： 10.1016/j.tcs.2013.11.030 　

  101. The minimum vulnerability problem on graphs 査読有り

    Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou

    Combinatorial Optimization and Applications - 8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014, Proceedings　299-313　2014年

    DOI： 10.1007/978-3-319-12691-3_23 　

  102. The list coloring reconfiguration problem for bounded pathwidth graphs 査読有り

    Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

    Combinatorial Optimization and Applications - 8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014, Proceedings　314-328　2014年

    DOI： 10.1007/978-3-319-12691-3_24 　

  103. Swapping labeled tokens on graphs 査読有り

    Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, Takeaki Uno

    Fun with Algorithms - 7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings　364-375　2014年

    DOI： 10.1007/978-3-319-07890-8_31 　

  104. Minimum-cost b-edge dominating sets on trees 査読有り

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

    Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings　195-207　2014年

    DOI： 10.1007/978-3-319-13075-0_16 　

  105. Fixed-parameter tractability of token jumping on planar graphs 査読有り

    Takehiro Ito, Marcin Kamiński, Hirotaka Ono

    Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings　208-219　2014年

    DOI： 10.1007/978-3-319-13075-0_17 　

  106. Polynomial-time algorithm for sliding tokens on trees 査読有り

    Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada

    Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings　389-400　2014年

    DOI： 10.1007/978-3-319-13075-0_31 　

  107. Reconfiguration of vertex covers in a graph 査読有り

    Takehiro Ito, Hiroyuki Nooka, Xiao Zhou

    Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers　164-175　2014年

    DOI： 10.1007/978-3-319-19315-1_15 　

  108. Deterministic algorithms for the independent feedback vertex set problem 査読有り

    Yuma Tamura, Takehiro Ito, Xiao Zhou

    Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers　351-363　2014年

    DOI： 10.1007/978-3-319-19315-1_31 　

  109. On the parameterized complexity for token jumping on graphs 査読有り

    Takehiro Ito, Marcin Kamiński, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, Katsuhisa Yamanaka

    Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014. Proceedings　341-351　2014年

    DOI： 10.1007/978-3-319-06089-7_24 　

  110. Route-enabling graph orientation problems 査読有り

    Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki, Ryuhei Uehara

    Algorithmica　65　(2)　317-338　2013年

    DOI： 10.1007/s00453-011-9589-z 　

  111. On the rainbow connectivity of graphs: Complexity and FPT algorithms 査読有り

    Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, Xiao Zhou

    Algorithmica　67　(2)　161-179　2013年

    DOI： 10.1007/s00453-012-9689-4 　

  112. On the minimum caterpillar problem in digraphs 査読有り

    Taku Okada, Akira Suzuki, Takehiro Ito, Xiao Zhou

    Computing and Combinatorics, 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. Proceedings　729-736　2013年

    DOI： 10.1007/978-3-642-38768-5_66 　

  113. Complexity of finding maximum regular induced subgraphs with prescribed degree 査読有り

    Yuichi Asahiro, Hiroshi Eto, Takehiro Ito, Eiji Miyano

    Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings　28-39　2013年

    DOI： 10.1007/978-3-642-40164-0_6 　

  114. Base location problems for base-monotone regions 査読有り

    Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno

    WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings　53-64　2013年

    DOI： 10.1007/978-3-642-36065-7_7 　

  115. Generalized rainbow connectivity of graphs 査読有り

    Kei Uchizawa, Takanori Aoki, Takehiro Ito, Xiao Zhou

    WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings　233-244　2013年

    DOI： 10.1007/978-3-642-36065-7_22 　

  116. Partitioning a weighted tree into subtrees with weights in a given range 査読有り

    Takehiro Ito, Takao Nishizeki, Michael Schröder, Takeaki Uno, Xiao Zhou

    Algorithmica　62　(3月4日)　823-841　2012年

    DOI： 10.1007/s00453-010-9485-y 　

  117. Minimum cost partitions of trees with supply and demand 査読有り

    Takehiro Ito, Takuya Hara, Xiao Zhou, Takao Nishizeki

    Algorithmica　64　(3)　400-415　2012年

    DOI： 10.1007/s00453-011-9573-7 　

  118. Reconfiguration of list edge-colorings in a graph 査読有り

    Takehiro Ito, Marcin Kamiński, Erik D. Demaine

    Discrete Applied Mathematics　160　(15)　2199-2207　2012年

    DOI： 10.1016/j.dam.2012.05.014 　

  119. An improved sufficient condition for reconfiguration of list edge-colorings in a tree 査読有り

    Takehiro Ito, Kazuto Kawamura, Xiao Zhou

    IEICE Transactions　95-D　(3)　737-745　2012年

    DOI： 10.1587/transinf.E95.D.737 　

  120. Packing trominoes is NP-complete, #P-complete and ASP-complete 査読有り

    Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, Ryuhei Uehara

    Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG 2012, Charlottetown, Prince Edward Island, Canada, August 8-10, 2012　211-216　2012年

  121. Reconfiguration of list L(2, 1)-labelings in a graph 査読有り

    Takehiro Ito, Kazuto Kawamura, Hirotaka Ono, Xiao Zhou

    Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings　34-43　2012年

    DOI： 10.1007/978-3-642-35261-4_7 　

  122. A 4.31-approximation for the geometric unique coverage problem on unit disks 査読有り

    Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings　372-381　2012年

    DOI： 10.1007/978-3-642-35261-4_40 　

  123. A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares 査読有り

    Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

    Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings　24-35　2012年

    DOI： 10.1007/978-3-642-31155-0_3 　

  124. On disconnected cuts and separators 査読有り

    Takehiro Ito, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos

    Discrete Applied Mathematics　159　(13)　1345-1351　2011年

    DOI： 10.1016/j.dam.2011.04.027 　

  125. Minimum cost edge-colorings of trees can be reduced to matchings 査読有り

    Takehiro Ito, Naoki Sakamoto, Xiao Zhou, Takao Nishizeki

    IEICE Transactions　94-D　(2)　190-195　2011年

    DOI： 10.1587/transinf.E94.D.190 　

  126. On the complexity of reconfiguration problems 査読有り

    Takehiro Ito, Erik D. Demaine, Nicholas J, A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno

    Theoretical Computer Science　412　(12-14)　1054-1065　2011年

    DOI： 10.1016/j.tcs.2010.12.005 　

  127. Parameterizing cut sets in a graph by the number of their components 査読有り

    Takehiro Ito, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos

    Theoretical Computer Science　412　(45)　6340-6350　2011年

    DOI： 10.1016/j.tcs.2011.07.005 　

  128. On the rainbow connectivity of graphs: Complexity and FPT algorithms 査読有り

    Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, Xiao Zhou

    Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings　86-97　2011年

    DOI： 10.1007/978-3-642-22685-4_8 　

  129. Approximability of the subset sum reconfiguration problem 査読有り

    Takehiro Ito, Erik D. Demaine

    Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings　58-69　2011年

    DOI： 10.1007/978-3-642-20877-5_7 　

  130. An improved sufficient condition for reconfiguration of list edge-colorings in a tree 査読有り

    Takehiro Ito, Kazuto Kawamura, Xiao Zhou

    Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings　94-105　2011年

    DOI： 10.1007/978-3-642-20877-5_10 　

  131. Minimum cost edge-colorings of trees can be reduced to matchings 査読有り

    Takehiro Ito, Naoki Sakamoto, Xiao Zhou, Takao Nishizeki

    Frontiers in Algorithmics, 4th International Workshop, FAW 2010, Wuhan, China, August 11-13, 2010. Proceedings　274-284　2010年

    DOI： 10.1007/978-3-642-14553-7_26 　

  132. Minimum cost partitions of trees with supply and demand 査読有り

    Takehiro Ito, Takuya Hara, Xiao Zhou, Takao Nishizeki

    Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part II　351-362　2010年

    DOI： 10.1007/978-3-642-17514-5_30 　

  133. Partitioning graphs of supply and demand 査読有り

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

    Discrete Applied Mathematics　157　(12)　2620-2633　2009年

    DOI： 10.1016/j.dam.2008.08.012 　

  134. A characterization of graphs with fractional total chromatic number equal to Delta+2 査読有り

    Takehiro Ito, W. Sean Kennedy, Bruce A. Reed

    Electronic Notes in Discrete Mathematics　35　235-240　2009年

    DOI： 10.1016/j.endm.2009.11.039 　

  135. Route-enabling graph orientation problems 査読有り

    Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki, Ryuhei Uehara

    Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings　403-412　2009年

    DOI： 10.1007/978-3-642-10631-6_42 　

  136. Parameterizing cut sets in a graph by the number of their components 査読有り

    Takehiro Ito, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos

    Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings　605-615　2009年

    DOI： 10.1007/978-3-642-10631-6_62 　

  137. Reconfiguration of list edge-colorings in a graph 査読有り

    Takehiro Ito, Marcin Kamiński, Erik D. Demaine

    Algorithms and Data Structures, 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings　375-386　2009年

    DOI： 10.1007/978-3-642-03367-4_33 　

  138. Approximability of partitioning graphs with supply and demand 査読有り

    Takehiro Ito, Erik D. Demaine, Xiao Zhou, Takao Nishizeki

    Journal of Discrete Algorithms　6　(4)　627-650　2008年

    DOI： 10.1016/j.jda.2008.03.002 　

  139. On the complexity of reconfiguration problems 査読有り

    Takehiro Ito, Erik D. Demaine, Nicholas J, A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno

    Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings　28-39　2008年

    DOI： 10.1007/978-3-540-92182-0_6 　

  140. Partitioning a weighted tree to subtrees of almost uniform size 査読有り

    Takehiro Ito, Takeaki Uno, Xiao Zhou, Takao Nishizeki

    Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings　196-207　2008年

    DOI： 10.1007/978-3-540-92182-0_20 　

  141. Partitioning a multi-weighted graph to connected subgraphs of almost uniform size 査読有り

    Takehiro Ito, Kazuya Goto, Xiao Zhou, Takao Nishizeki

    IEICE Transactions　90-D　(2)　449-456　2007年

    DOI： 10.1093/ietisy/e90-d.2.449 　

  142. Algorithms for finding distance-edge-colorings of graphs 査読有り

    Takehiro Ito, Akira Kato, Xiao Zhou, Takao Nishizeki

    Journal of Discrete Algorithms　5　(2)　304-322　2007年

    DOI： 10.1016/j.jda.2006.03.020 　

  143. Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size 査読有り

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

    Journal of Discrete Algorithms　4　(1)　142-154　2006年

    DOI： 10.1016/j.jda.2005.01.005 　

  144. Partitioning a multi-weighted graph to connected subgraphs of almost uniform size 査読有り

    Takehiro Ito, Kazuya Goto, Xiao Zhou, Takao Nishizeki

    Computing and Combinatorics, 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings　63-72　2006年

    DOI： 10.1007/11809678_9 　

  145. Approximability of partitioning graphs with supply and demand 査読有り

    Takehiro Ito, Erik D. Demaine, Xiao Zhou, Takao Nishizeki

    Algorithms and Computation, 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings　121-130　2006年

    DOI： 10.1007/11940128_14 　

  146. Partitioning trees of supply and demand 査読有り

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

    International Journal of Foundations of Computer Science　16　(4)　803-827　2005年

    DOI： 10.1142/S0129054105003303 　

  147. Algorithms for finding distance-edge-colorings of graphs 査読有り

    Takehiro Ito, Akira Kato, Xiao Zhou, Takao Nishizeki

    Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings　798-807　2005年

    DOI： 10.1007/11533719_81 　

  148. Partitioning graphs of supply and demand 査読有り

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

    International Symposium on Circuits and Systems (ISCAS 2005), 23-26 May 2005, Kobe, Japan　160-163　2005年

    DOI： 10.1109/ISCAS.2005.1464549 　

  149. Partitioning a weighted graph to connected subgraphs of almost uniform size 査読有り

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

    Graph-Theoretic Concepts in Computer Science, 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers　365-376　2004年

    DOI： 10.1007/978-3-540-30559-0_31 　

  150. Algorithms for multicolorings of partial k-trees 査読有り

    Takehiro Ito, Takao Nishizeki, Xiao Zhou

    IEICE Transactions　E86-D　(2)　191-200　2003年

  151. Algorithms for the multicolorings of partial k-trees 査読有り

    Takehiro Ito, Takao Nishizeki, Xiao Zhou

    Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002, Proceedings　430-439　2002年

    DOI： 10.1007/3-540-45655-4_46 　

  152. Partitioning trees of supply and demand 査読有り

    Takehiro Ito, Xiao Zhou, Takao Nishizeki

    Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings　612-623　2002年

    DOI： 10.1007/3-540-36136-7_53 　

︎全件表示 ︎最初の5件までを表示

産業財産権 6

  1. 配電系統制御装置

    杉村 修平, 田邊 隆之, 周 暁, 伊藤 健洋, 鈴木 顕

    特許第7336359号

    産業財産権の種類: 特許権

  2. 配電系統制御装置

    杉村 修平, 田邊 隆之, 周 暁, 伊藤 健洋, 鈴木 顕, 畠山 航

    特許第7303500号

    産業財産権の種類: 特許権

  3. 配電系統制御装置

    杉村 修平, 田邊 隆之, 周 暁, 伊藤 健洋, 鈴木 顕, 千葉 詩音

    特許第7145109号

    産業財産権の種類: 特許権

  4. 配電自動化システムの電力融通方法

    西関 隆夫, 周 暁, 伊藤 健洋, 南部 淳, 伊藤 孝充, 田中 哲司

    特許第4622968号

    産業財産権の種類: 特許権

  5. 電力融通システム、電力融通方法、電力融通プログラム

    伊藤 健洋, 鈴木 顕, 飯岡 大輔, 川原 純, 山岡 宙太, 杉村 修平, 田邊 隆之, 後藤 誠弥

    産業財産権の種類: 特許権

  6. 配電系統制御装置、配電系統制御方法

    杉村 修平, 田邊 隆之, 伊藤 健洋, 鈴木 顕

    産業財産権の種類: 特許権

︎全件表示 ︎最初の5件までを表示

共同研究・競争的資金等の研究課題 20

  1. 理論的に計算不能・計算困難なクラスの可解領域の研究

    上原 隆平, 湊 真一, 川原 純, 伊藤 健洋, 番原 睦則

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (A)

    研究機関：Japan Advanced Institute of Science and Technology

    2024年4月 ～ 2029年3月

  2. 解空間の形状に着目した組合せ遷移の理論：計算量解析の高精細化とソルバー新技法

    伊藤 健洋, 宋 剛秀, 小林 靖明, 野崎 雄太

    2024年4月 ～ 2028年3月

  3. 迂回の特性を捉えた最短遷移アルゴリズムに関する研究

    伊藤 健洋

    2019年4月1日 ～ 2025年3月31日

    詳細を見る 詳細を閉じる

    本年度は，Kempeら (2002年) が導入した時間ネットワークの概念において，その関連する遷移問題を研究した．この概念は，分散通信などネットワーク上の時間制約を解析するために導入され，時間ラベル付き有向グラフによって表現される．本研究では，時間制約付き有向全域木を対象とした遷移問題を解析した．これまでの研究に依って，時間制約の条件がない場合には，無向グラフであっても有向グラフであっても，任意の2つの全域木は互いに遷移可能であると知られている．すなわち，これら全域木からなる解空間グラフは常に連結である．加えて，無向・有向のいずれのグラフであっても，全域木の最短遷移問題も多項式時間で解けることが知られている．それとは対照的に，本研究では，時間制約を導入した場合には，解空間グラフは非連結となり得ることをまず示した．次に，そのような解空間グラフであっても，与えられた2つの時間制約付き有向全域木が互いに遷移可能であるかどうか（すなわち，到達判定）が，多項式時間で解けることを示した．その一方で，時間制約がある場合には最短遷移問題がNP困難であることを示し，時間制約の有無に依って計算複雑性が変わるという対比を示すことができた． 本年度は他にも，グラフ上のラベル付きトークン遷移問題に関する研究も行った．この問題では多項式長の遷移系列の存在が示せるため，最短遷移問題が研究対象となる．この問題は，量子プログラムのコンパイラ設計に現れる量子ビットルーティング問題として，これまでも研究されてきた．既存研究では実践的なアプローチが主であったが，本研究では計算複雑性の理論的な解析に取り組み，NP困難性や特殊ケースにおける多項式時間アルゴリズム等を開発した．

  4. 組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合

    伊藤 健洋, 川原 純, 岡本 吉央, 鈴木 顕

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Transformative Research Areas (B)

    研究機関：Tohoku University

    2020年10月2日 ～ 2023年3月31日

    詳細を見る 詳細を閉じる

    計算機科学・工学・数学を背景分野とする研究者らが円滑に共同研究を進め，その研究成果を外部に広くアピールするために，研究領域のマネジメントを行った．班間連携の促進のため，領域会議 (6回)，セミナー・勉強会 (35回) を開催し，ニュースレター (5号) を発行した．これらは一般公開した．また，様々な分野でイベントを多数開催した．国際会議ICALPでの併設ワークショップ (3回)，オンラインOne-Day国際ワークショップ (4回)，組合せ遷移の国際プログラミング競技会 (2回)，組合せ遷移の学生シンポジウム (2回)，出前イベント (4回) と多岐にわたる．

  5. 計算機科学アプローチによる組合せ遷移の展開：アルゴリズムの自動生成に向けて

    伊藤 健洋, 和佐 州洋, 山内 由紀子, 小林 靖明, 大舘 陽太

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Transformative Research Areas (B)

    研究機関：Tohoku University

    2020年10月2日 ～ 2023年3月31日

    詳細を見る 詳細を閉じる

    計算機科学を背景分野とする本計画研究では，繰越期間を含む3.5年間に査読付き学術論文を73件発表した．これらの研究に依り，様々な組合せ遷移問題に対するアルゴリズムの事例研究を推進できただけでなく，大目標に掲げていた「組合せ遷移のアルゴリズム的メタ定理」の構築にも成功した．また，近接分野である列挙や分散計算の手法を組合せ遷移に取り入れ，それを還元することで生まれた成果もある．さらには，他の計画研究班や領域外の研究者らと協働し，組合せ遷移のアルゴリズム理論の様々な展開にも取り組むことができた．

  6. 理論的に困難な問題を現実的な時間で解くアルゴリズムとデータ構造の研究

    上原 隆平, 齋藤 寿樹, 鈴木 顕, 川原 純, 伊藤 健洋, 山中 克久, 吉仲 亮, 大舘 陽太

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (A)

    研究機関：Japan Advanced Institute of Science and Technology

    2018年4月1日 ～ 2023年3月31日

    詳細を見る 詳細を閉じる

    近年、コンピュータの機能向上は著しい。しかし一般のユーザの想像に反して、コンピュータが問題を解く速度が向上している原因の主要なファクターは、ハードウェアの性能向上ではなく、その上のソフトウェア、特にアルゴリズムやデータ構造の発展の方が多大な貢献をしている。本研究テーマでは、様々な組合せ最適化問題に対して、まず理論的な困難性を示し、そのプロセスで明らかになった問題の性質を用いることで、問題を効率よく解くためのアルゴリズムを設計・開発した。

  7. 組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合

    伊藤 健洋

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Transformative Research Areas (B)

    2020年10月 ～ 2023年3月

  8. 組合せ遷移に対するアルゴリズム技法の開発

    伊藤 健洋, 小林 佑輔, 和佐 州洋, 水田 遥河

    提供機関：Japan Society for the Promotion of Science

    制度名：Bilateral Collaborations

    2018年4月 ～ 2020年3月

  9. 不満度を最小化する運搬経路問題に対するグラフアルゴリズム手法とその一般化

    伊藤 健洋

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    2016年4月1日 ～ 2019年3月31日

    詳細を見る 詳細を閉じる

    サービス受給側の不満度を評価対象とする比較的新しい設定の運搬経路問題について，入力グラフの構造を利用したアルゴリズムの開発を行い，それと対比をなす計算困難性や近似不可能性の証明も行った．加えて，問題設定の一般化を行うことで，開発手法の拡張を考察し，アルゴリズム手法の整備を行った．特に，本研究の木に対する近似手法は，近似解の精度をアルゴリズムの利用者が任意に指定することができるため，精度の観点からは最良といえる．

  10. 解空間のパラメータ化解析による計算困難性と容易性の解明

    伊藤 健洋

    2015年4月1日 ～ 2017年3月31日

    詳細を見る 詳細を閉じる

    本年度は，シュタイナー木の遷移問題について，その計算困難性と容易性を解析した．特に，スプリットグラフでは計算困難であるが，区間グラフでは計算容易であることを示しており，グラフ構造の観点から興味深い対比を与えている．すなわち，スプリットグラフはクリークが木（スター）構造を成しているグラフであり，区間グラフはクリークがパス構造を成しているグラフである．どちらのグラフも辺が密であり，比較的近い構造を持つが，その計算複雑さに差があることを示した． また，（リスト）辺彩色の遷移問題について，その計算困難性を示した．辺ごとに使用可能な色が限定されない辺彩色の遷移問題については，その計算困難性が一切知られていなかったが，本研究では初めて計算困難性を示すことに成功した．辺ごとに使用可能な色集合が与えられるリスト辺彩色の遷移問題は，従来研究では，彩色に使用できる色数が３色以下であれば計算容易であり，６色以上であれば計算困難であることが知られていた．すなわち，色数が４色と５色の場合は未解決であったが，本研究では，どちらも計算困難であることを証明した．これにより，色数に基づく計算困難性と容易性を完全に特徴づけることに成功した． これら（リスト）辺彩色の遷移問題に関する計算困難性の証明は，遷移問題における帰着手法の特徴を与えることで達成している．すなわち，帰着を構成する際に，解空間の連結性を「内部連結」と「外部連結」という二つの概念を用いて保証した．これにより，複雑な帰着の正当性を計算機によって検証することを可能とした．実際，本研究で与えた証明では，可能な辺彩色が約３０万種類もあり，計算機による検証なしでは証明は難しかったであろう．

  11. ネットワークの余力を最大化するサーバ割当アルゴリズムの開発

    伊藤 健洋

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    2013年4月1日 ～ 2016年3月31日

    詳細を見る 詳細を閉じる

    ネットワークにおいて回線帯域を逼迫しないようなサーバからユーザへのデータ配信方法を求める問題を，グラフにおける組合せ問題として定式化し研究した．特に，グラフ構造の観点からこのサーバ割当問題の計算困難性と容易性の解析を進め，グラフ中の閉路の個数やサーバの個数が計算可能性に与える影響を明らかにした．多くの場合，この問題は計算困難であるため，本研究課題では，動的計画法に基づく擬多項式時間アルゴリズムや固定パラメータアルゴリズムを与えた．

  12. 解空間の直径に基づく計算限界解析アプローチの構築

    伊藤 健洋

    2013年4月1日 ～ 2015年3月31日

    詳細を見る 詳細を閉じる

    本年度は，点彩色を一般化した「リスト点彩色」の遷移問題に対して，詳細な解析を与えることができた．グラフ構造の指標として「パス幅」と呼ばれるパラメータがあるが，パス幅が2以上であればリスト点彩色の遷移問題はPSPACE完全であり，パス幅が1であれば多項式時間で解けることを示した．すなわち，これはリスト点彩色の遷移問題の計算困難性と容易性を，入力グラフのパス幅の観点から特徴づけたことになる．パス幅1の入力グラフに対する多項式時間アルゴリズムは動的計画法に基づいており，遷移問題に対して動的計画法を適用した例としても評価できる． <br> また，独立点集合の遷移問題に対しては，固定パラメータ容易性（FPT）の観点から，研究を進めることができた．この問題は，平面グラフにおいてPSPACE完全であることが示されており，解空間グラフの直径は超多項式長になる．しかし本研究では，独立点集合のサイズのみをパラメータとして，平面グラフに対するFPTアルゴリズムを与えた．この研究成果により，解空間グラフの直径が超多項式長になることを単に示すだけでなく，パラメータにどのように依存するのか解析することができた．特に，本研究では昨年度，一般のグラフに対しては，独立点集合のサイズのみをパラメータとしたFPTアルゴリズムを持ちそうにないことを証明しており，今年度の研究と対比させることで，入力グラフの構造と計算困難性の関係をより具体的に解析することができた． <br> この他にも，点彩色と関連が深いL(2,1)ラベリングなど，様々な遷移問題に対してアルゴリズムを開発することで，解空間グラフの直径が多項式長で抑えられる場合を明らかにし，計算困難である場合との対比を可能とした．特に，本研究では，入力グラフの構造を上手く利用することで，効率のよいアルゴリズムを多数開発することができた．

  13. グラフを分割，彩色，描画するアルゴリズムの効率化とそれらの応用

    西関 隆夫, 周 暁, 伊藤 健洋, 内沢 啓

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    2009年4月1日 ～ 2014年3月31日

    詳細を見る 詳細を閉じる

    グラフの分割，彩色あるいは描画する問題の最適解や近似解を求める効率のよいアルゴリズムを開発するとともに，それらを実用的な問題に応用した．代表的な成果の一例を挙げる．点重み付きグラフGと正整数pが与えられたときに，何本かの辺を除去してGをp個の連結成分に分割し，各成分の点重みの合計をできるだけ公平にするアルゴリズムを木幅限定グラフに対し開発した．

  14. 解の遷移可能性問題による停止しないシステムの実現

    伊藤 健洋

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Young Scientists (B)

    研究機関：Tohoku University

    2010年 ～ 2012年

    詳細を見る 詳細を閉じる

    本研究では,「解空間の連結性」を問う遷移可能性問題を研究した.特に,計算機科学の基礎的な問題である「ナップザック問題」と電力系統の配電融通問題に応用がある「需要と供給のグラフ分割問題」に対する遷移可能性問題を扱い,その計算困難性を明らかにし,さらに遷移方法を求める近似アルゴリズムを開発した.本研究で開発した近似アルゴリズムは,近似精度の観点からは最良である.

  15. 発見的手法による「人が待てる」アルゴリズムの開発

    伊藤 健洋

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Young Scientists (B)

    研究機関：Tohoku University

    2008年 ～ 2009年

    詳細を見る 詳細を閉じる

    本研究では,理論研究によるアルゴリズム開発を行うだけでなく,開発したアルゴリズムに発見的手法を組み合わせることで,「人が待てる」高速なアルゴリズムの開発まで一貫して行った.電力系統の配電融通問題などに応用がある「需要と供給のグラフ分割問題」に対しては,近似アルゴリズムを与え,発見的手法と組み合わせることで,瞬時に分割を求めることに成功した.一方で,選挙区割問題や画像処理などに応用がある「グラフの均一分割問題」に対しては,最適解を多項式時間で求めるアルゴリズムを与えることに成功した.

  16. VLSI設計へのグラフ描画アルゴリズムの応用

    西関 隆夫, 周 暁, 伊藤 健洋, 内沢 啓, 周 暁, 伊藤 健洋

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    2007年 ～ 2008年

    詳細を見る 詳細を閉じる

    これまでに平面グラフの埋め込みアルゴリズム, 矩形描画アルゴリズム, 凸描画アルゴリズム, 4連結平面グラフの直線描画アルゴリズム, 直交描画アルゴリズムなど数多くの効率のよいアルゴリズムを開発してきた。これらのもとに, 新しい描画形式である内部矩形描画, 面積指定8角形描画, 折れ曲り数最小な直交描画等に関する理論を確立し, 効率のよいアルゴリズムを開発し, VLSI配置・配線問題への応用を図った.

  17. グラフ分割アルゴリズムの新しい設計手法に関する研究

    伊藤 健洋

    2006年 ～ 2007年

    詳細を見る 詳細を閉じる

    本年度は,主に選挙区割問題などに応用がある「グラフの均一分割問題」について研究を行った.この問題は,点に整数の重みが付いたグラフが与えられたとき,グラフから辺を削除し,各連結成分に含まれる点の重みの合計が均一になるように分割する問題である.本研究では,各点に2つ以上の重みが与えられていても,部分k木の均一分割問題が擬多項式時間で解けることを示した.また,2つ以上与えられた点の重みのうち,分割を求める際には1つだけを自由に選択できる場合についても考察を行い,擬多項式時間アルゴリズムを与えることができた.これらの結果は,IEICE Trans.on Information and Systemsに掲載になった. また,電力系統の配電融通問題などに応用がある「需要点と供給点のあるグラフの分割問題」も研究を進めた.この問題は,需要点と供給点のあるグラフに対し,電力が供給されない需要点ができてしまうとき,供給されている需要点の需要量の合計を最大にする最大化問題である.この問題の近似可能性を明らかにした論文を,海外の学術雑誌に投稿した.

  18. グラフ描画アルゴリズムとそのWeb情報検索への応用

    西関 隆夫, 周 暁, 伊藤 健洋, 三浦 一之, 浅野 泰仁

    2004年 ～ 2007年

    詳細を見る 詳細を閉じる

    (1)平面的グラフの折れ曲がりなし直交描画問題について,グラフが3連結立方グラフの細分であれば,折れ曲がりなし直交描画を線形時間で求めることのできるアルゴリズムを与えた. (2)直並列グラフの直交描画で折れ曲り数最少のものを求める線形アルゴリズムを開発した. (3)平面グラフの格子凸描画において,別個に研究されてきた標準分解,リアライザ,シュナイダーラベリング,順序つき全域木がすべて同等であることを証明した. (4)VLSIレイアウトに平面グラフの内部矩形描画が応用できる.与えられた平面グラフが内部矩形描画できるかどうか判定し,できるならば内部矩形描画を高速に求めるアルゴリズムを与えた. (5)電力供給問題のモデル化であり,一般には強NP困難問題として知られる,需要・供給付きグラフの分割問題について研究し,分割数を最少・最多にする問題,および指定された個数の連結成分への分割を求める問題に対して,グラフが木(または部分k-木)であるときに厳密解を求める多項式時間(または擬似多項式時間)アルゴリズムを与えた. (6)購入した計算機を用いてウェブ文書データを解析し,サイトのデータを抽出し,このデータからサイトを点とするサイト間グラフを構築した.さらに,サイト間グラフの特徴を利用して,著名な情報検索手法であるmax-flow based methodの品質を大幅に改善する手法を確立し,実験によってその性能を検証した.

  19. 効率的グラフアルゴリズムの統一的設計理論に関する研究

    西関 隆夫, 周 暁, 伊藤 健洋, 浅野 泰仁

    提供機関：Japan Society for the Promotion of Science

    制度名：Grants-in-Aid for Scientific Research

    研究種目：Grant-in-Aid for Scientific Research (C)

    研究機関：Tohoku University

    2005年 ～ 2006年

    詳細を見る 詳細を閉じる

    本研究では,木,直並列グラフ,部分k-木等の構造的グラフに対し,彩色問題,素な道問題,グラフ描画問題を取り上げ,個々の問題に対して効率のよいアルゴリズムを設計するばかりでなく,構造的グラフに対する効率的アルゴリズムの統一的設計法の研究開発を行った. まず,木に対しては,需要点と供給点があるときの分割問題を解く完全近似スキームを与えることができた. 直並列グラフに対しては,リスト全彩色が存在するための十分条件を与えるとともに,その条件を満足する場合にリスト全彩色を線形時間で求めるアルゴリズムを開発した. 次に,部分k-木に対しては,全彩色問題を解く線形時間アルゴリズム,均一分割問題を解く擬多項式時間アルゴリズム,需要点と供給点のあるグラフの分割問題を解く擬多項式時間アルゴリズムの開発に成功した. また,グラフ描画アルゴリズムでは,直並列グラフの折れ曲り数最少の直交描画を求める線形アルゴリズムを設計するとともに,グラフの凸描画問題に応用することができるグラフの分解法も与えた. 本年度は,構造的グラフに対する効率的アルゴリズムの統一的設計法の開発を目指した研究を行い,これまでさまざまな問題に対するより高速なアルゴリズムの開発に成功しており,一般の辺素部分グラフ分解問題に対する効率のよいアルゴリズムの統一的理論構築のために基盤作りに十分な成果をあげることができ,得られた成果を論文としてまとめ,論文誌では7編,国際会議では5編発表した.

  20. グラフの多重彩色及び分割に関するアルゴリズム

    伊藤 健洋

    2003年 ～ 2005年

    詳細を見る 詳細を閉じる

    本研究では,グラフの点に供給点または需要点の役割が与えられ,それぞれに供給量と需要量という重みが与えられた重み付きグラフを扱った.そのようなグラフに対し,需要と供給の条件を満たすようにグラフを分割するアルゴリズムを開発した. まず,木のグラフ分割問題に関してまとめた論文が,学術雑誌に採録された. 次に,直並列グラフと呼ばれるグラフのクラスに対し,グラフ分割問題を解くアルゴリズムの開発・解析を行った.グラフ分割問題は木に対してさえNP困難であり,したがって直並列グラフに対し効率のよいアルゴリズムはありそうにない.そこで,本研究では擬多項式時間アルゴリズムの開発を行った.その結果は,2005年5月開催の国際会議にて発表し,現在学術雑誌に投稿中である. また,直並列グラフに対し,より一般的な分割問題を解くアルゴリズムを与えた.この問題では,今まで上限のみ指定することができた連結成分の重みの和の制限を,上限と下限の両方を同時に指定することができるようにした.さらに,グラフの点に複数個の重みが割当てられている場合にも,効率よく解けることを示した.この結果は,現在国際会議に投稿するように準備中である.

︎全件表示 ︎最初の5件までを表示