研究者詳細

顔写真

スズキ　アキラ
鈴木　顕
Akira Suzuki
所属
データ駆動科学・ＡＩ教育研究センター　ＡＩ教育研究部門
職名
教授
学位

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

経歴 4

  • 2025年4月 ～ 継続中
    東北大学 データ駆動科学・AI教育研究センター　教授

  • 2019年5月 ～ 2025年3月
    東北大学 大学院情報科学研究科　准教授

  • 2013年10月 ～ 2019年4月
    東北大学 大学院情報科学研究科　助教

  • 2012年4月 ～ 2013年9月
    日本学術振興会 特別研究員（DC1）

学歴 4

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

    2011年10月 ～ 2013年9月

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

    2010年4月 ～ 2011年9月

  • 東北大学　工学部　電気情報物理工学科

    2006年4月 ～ 2010年3月

  • 渋谷教育学園 幕張高等学校

    2003年4月 ～ 2006年9月

委員歴 12

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

    2026年6月 ～ 継続中

  • 東北大学 データ駆動科学・AI教育研究センター AI教育研究部門　部門長

    2026年4月 ～ 継続中

  • 東北大学 データ駆動科学・AI教育研究センター　副センター長

    2026年4月 ～ 継続中

  • 電子情報通信学会 英文誌D　編集委員

    2022年 ～ 継続中

  • 情報処理学会 東北支部　支部委員

    2024年6月 ～ 2026年6月

  • LAシンポジウム　事務局

    2025年4月 ～ 2026年3月

  • 情報処理学会　代表会員

    2023年4月 ～ 2025年3月

  • 情報処理学会 アルゴリズム研究会　幹事

    2020年5月 ～ 2024年5月

  • 情報処理学会 東北支部　庶務幹事

    2022年6月 ～ 2023年6月

  • LAシンポジウム　事務局

    2017年4月 ～ 2018年3月

  • 中高生情報学研究コンテスト　審査員

    2023年 ～

  • 電気関係学会東北支部連合大会　主幹事

    2022年 ～

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

所属学協会 2

  • 電子情報通信学会

    2012年4月 ～ 継続中

  • 情報処理学会

    2018年4月 ～ 2025年3月

研究キーワード 3

  • 組合せ遷移

  • グラフアルゴリズム

  • 計算の複雑さ

研究分野 1

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

受賞 12

  1. Best Paper Award

    2025年2月　The 19th International Conference and Workshops on Algorithms and Computation (WALCOM 2025)

  2. 令和5年度 総長教育賞

    2024年3月　東北大学

  3. 令和5年度 全学教育貢献賞

    2024年1月　東北大学

  4. 2023年度 研究奨励賞

    2023年10月　石田實記念財団

  5. 第14回 野口研究奨励賞

    2019年6月　情報処理学会東北支部

  6. 第14回 船井研究奨励賞

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

  7. 第25回 トーキン財団奨励賞

    2015年3月5日　トーキン科学技術振興財団

  8. 第31回 井上研究奨励賞

    2015年2月4日　井上科学振興財団

  9. 総長賞

    2014年3月26日　東北大学

  10. 情報科学研究科長賞

    2014年3月26日　東北大学 大学院情報科学研究科

  11. 平成24年度 学術奨励賞

    2013年3月20日　電子情報通信学会

  12. 電気・情報系優秀賞

    2012年3月27日　東北大学

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

論文 114

  1. Finding shortest reconfiguration sequence on independent set polytopes 査読有り

    Takahiro Suzuki, Jean Cardinal, Kevin Mann, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 51st International Symposium on Mathematical Foundations of Computer Science (MFCS 2026), Leibniz International Proceedings in Informatics (LIPIcs)　386　37:1-37:19　2026年8月

    DOI： 10.4230/LIPIcs.MFCS.2026.37 　

  2. On the complexity of k-colorable perfect matching 査読有り

    Toranosuke Kokai, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 32nd International Computing and Combinatorics Conference (COCOON 2026), Lecture Notes in Computer Science (LNCS)　16835　288-300　2026年7月15日

    出版者・発行元： Springer Nature Singapore

    DOI： 10.1007/978-981-92-3309-0_22 　

    ISSN：0302-9743

    eISSN：1611-3349

  3. Computational complexity of swish is solved 査読有り

    Takashi Horiyama, Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Akira Suzuki, Ryuhei Uehara, Yutaro Yamaguchi

    Proceedings of the 30th International Conference on Fun with Algorithms (FUN 2026), Leibniz International Proceedings in Informatics (LIPIcs)　366　25:1-25:12　2026年5月

    DOI： 10.4230/LIPIcs.FUN.2026.25 　

  4. Spanning trees with a small vertex cover the complexity on specific graph classes 査読有り

    Toranosuke Kokai, Akira Suzuki, Takahiro Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 51st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2026), Lecture Notes in Computer Science (LNCS)　16448　578-592　2026年2月13日

    出版者・発行元： Springer Nature Switzerland

    DOI： 10.1007/978-3-032-17801-5_42 　

    ISSN：0302-9743

    eISSN：1611-3349

  5. Reconfiguration of time-respecting arborescences 招待有り 査読有り

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

    Algorithmica　88　(1-15)　1-16　2025年12月22日

    出版者・発行元： Springer Science and Business Media LLC

    DOI： 10.1007/s00453-025-01365-1 　

    ISSN：0178-4617

    eISSN：1432-0541

  6. Reachability of independent sets and vertex covers under extended reconfiguration rules 査読有り

    Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 36th International Symposium on Algorithms and Computation (ISAAC 2025), Leibniz International Proceedings in Informatics (LIPIcs)　359　39:1-39:20　2025年12月

    DOI： 10.4230/LIPIcs.ISAAC.2025.39 　

  7. Changing induced subgraph isomorphisms under extended reconfiguration rules 招待有り 査読有り

    Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Information and Computation　307　(105367)　1-21　2025年11月

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.ic.2025.105367 　

    ISSN：0890-5401

  8. Spanning Trees with a Small Vertex Cover: the Complexity on Specific Graph Classes.

    Toranosuke Kokai, Akira Suzuki 0001, Takahiro Suzuki 0002, Yuma Tamura, Xiao Zhou 0001

    CoRR　abs/2511.22912　2025年11月

    DOI： 10.48550/arXiv.2511.22912 　

  9. Reachability of Independent Sets and Vertex Covers Under Extended Reconfiguration Rules.

    Shuichi Hirahara, Naoto Ohsaka, Tatsuhiro Suga, Akira Suzuki 0001, Yuma Tamura, Xiao Zhou 0001

    CoRR　abs/2510.24226　2025年10月

    DOI： 10.48550/arXiv.2510.24226 　

  10. On the complexity of list H-packing for sparse graph classes 査読有り

    Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Yota Otachi, Tomohito Shirai, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Theoretical Computer Science　1052　(115425)　1-18　2025年10月

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.tcs.2025.115425 　

    ISSN：0304-3975

  11. Parameterized complexity of weighted target set selection 査読有り

    Takahiro Suzuki, Kei Kimura, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Theoretical Computer Science　1051　(115414)　1-19　2025年10月

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.tcs.2025.115414 　

    ISSN：0304-3975

  12. Homotopy types of Hom complexes of graph homomorphisms whose codomains are cycles 査読有り

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Yuta Nozaki, Akira Suzuki

    Journal of Applied and Computational Topology　9　(3-21)　1-21　2025年9月4日

    出版者・発行元： Springer Science and Business Media LLC

    DOI： 10.1007/s41468-025-00219-7 　

    ISSN：2367-1726

    eISSN：2367-1734

  13. Changing induced subgraph isomorphisms under extended reconfiguration rules 査読有り

    Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 19th International Conference and Workshops on Algorithms and Computation (WALCOM 2025), Lecture Notes in Computer Science (LNCS)　15411　346-360　2025年2月21日

    出版者・発行元： Springer Nature Singapore

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

    ISSN：0302-9743

    eISSN：1611-3349

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

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

    電気学会論文誌Ｂ（電力・エネルギー部門誌）　144　(12)　640-649　2024年12月1日

    出版者・発行元：

    DOI： 10.1541/ieejpes.144.640 　

    ISSN：0385-4213

    eISSN：1348-8147

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

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

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

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

    DOI： 10.4230/LIPIcs.SEA.2024.26 　

  16. Card-based zero-knowledge proof protocols for the 15-puzzle and the token swapping problem 査読有り

    Yuma Tamura, Akira Suzuki, Takaaki Mizuki

    Proceedings of the 11th ACM ASIA Public-Key Cryptography Workshop (APKC 2024) held in the 19th ACM ASIA Conference on Computer and Communications Security (ACM ASIACCS 2024)　11-22　2024年7月

    出版者・発行元： ACM

    DOI： 10.1145/3659467.3659905 　

  17. Finding induced subgraphs from graphs with small mim-width 査読有り

    Yota Otachi, Akira Suzuki, Yuma Tamura

    Proceedings of the 19th Scandinavian Symposium on Algorithm Theory (SWAT 2024), Leibniz International Proceedings in Informatics (LIPIcs)　294　38:1-38:16　2024年6月

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

    DOI： 10.4230/LIPIcs.SWAT.2024.38 　

  18. Parameterized complexity of weighted target set selection 査読有り

    Takahiro Suzuki, Kei Kimura, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 18th Annual Conference on Theory and Applications of Models of Computation (TAMC 2024), Lecture Notes in Computer Science (LNCS)　14637　320-331　2024年5月

    出版者・発行元： Springer

    DOI： 10.1007/978-981-97-2340-9_27 　

  19. On the complexity of list H-packing for sparse graph classes 査読有り

    Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Yota Otachi, Tomohito Shirai, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 18th International Conference and Workshops on Algorithms and Computation (WALCOM 2024), Lecture Notes in Computer Science (LNCS)　14549　421-435　2024年3月

    出版者・発行元： Springer

    DOI： 10.1007/978-981-97-0566-5_30 　

  20. The shortest path reconfiguration problem based on relaxation of reconfiguration rules 査読有り

    Naoki Domon, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 18th International Conference and Workshops on Algorithms and Computation (WALCOM 2024), Lecture Notes in Computer Science (LNCS)　14549　227-241　2024年2月29日

    出版者・発行元： Springer Nature Singapore

    DOI： 10.1007/978-981-97-0566-5_17 　

    ISSN：0302-9743

    eISSN：1611-3349

  21. Finding Induced Subgraphs from Graphs with Small Mim-Width.

    Yota Otachi, Akira Suzuki 0001, Yuma Tamura

    CoRR　abs/2405.15492　2024年

    DOI： 10.48550/arXiv.2405.15492 　

  22. On the Routing Problems in Graphs with Ordered Forbidden Transitions 査読有り

    Kota Kumakura, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 29th International Computing and Combinatorics Conference (COCOON 2023), Lecture Notes in Computer Science (LNCS)　14422　359-370　2024年

    出版者・発行元： Springer

    DOI： 10.1007/978-3-031-49190-0_26 　

    ISSN：0302-9743

    eISSN：1611-3349

  23. 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年11月6日

    出版者・発行元： IEEE

    DOI： 10.1109/ictai59109.2023.00050 　

  24. Feedback vertex set reconfiguration in planar graphs 査読有り

    Nicolas Bousquet, Felix Hommelsheim, Yusuke Kobayashi, Moritz Mühlenthaler, Akira Suzuki

    Theoretical Computer Science　979　(114188)　1-14　2023年11月

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.tcs.2023.114188 　

    ISSN：0304-3975

  25. 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)　1-15　2023年11月

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.tcs.2023.114158 　

    ISSN：0304-3975

  26. 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), Lecture Notes in Computer Science (LNCS)　13884　167-183　2023年5月23日

    出版者・発行元： Springer Nature Switzerland

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

    ISSN：0302-9743

    eISSN：1611-3349

  27. 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)　1-17　2023年5月

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.tcs.2023.113863 　

    ISSN：0304-3975

  28. Reconfiguration of Spanning Trees with Degree Constraints or Diameter Constraints 査読有り

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

    Algorithmica　85　(9)　2779-2816　2023年4月10日

    出版者・発行元： Springer Science and Business Media LLC

    DOI： 10.1007/s00453-023-01117-z 　

    ISSN：0178-4617

    eISSN：1432-0541

  29. Parameterized Complexity of Optimizing List Vertex-Coloring Through Reconfiguration 査読有り

    Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 17th International Conference and Workshops on Algorithms and Computation (WALCOM 2023), Lecture Notes in Computer Science (LNCS)　13973　279-290　2023年3月13日

    出版者・発行元： Springer Nature Switzerland

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

    ISSN：0302-9743

    eISSN：1611-3349

  30. Path Cover Problems with Length Cost 査読有り

    Kenya Kobayashi, Guohui Lin, Eiji Miyano, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, Tsuyoshi Yagita

    Algorithmica　85　(11)　3348-3375　2023年3月6日

    出版者・発行元： Springer Science and Business Media LLC

    DOI： 10.1007/s00453-023-01106-2 　

    ISSN：0178-4617

    eISSN：1432-0541

  31. Decremental optimization of vertex-colouring under the reconfiguration framework 査読有り

    Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

    International Journal of Computer Mathematics: Computer Systems Theory　8　(1)　80-92　2023年1月2日

    出版者・発行元： Informa UK Limited

    DOI： 10.1080/23799927.2023.2185543 　

    ISSN：2379-9927

    eISSN：2379-9935

  32. On the complexity of list H-packing for sparse graph classes.

    Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Yota Otachi, Tomohito Shirai, Akira Suzuki, Yuma Tamura, Xiao Zhou 0001

    CoRR　abs/2312.08639　2023年

    DOI： 10.48550/arXiv.2312.08639 　

  33. 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), Lecture Notes in Computer Science (LNCS)　14079　521-532　2023年

    出版者・発行元： Springer

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

  34. Reconfiguration of Time-Respecting Arborescences.

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

    CoRR　abs/2305.07262　2023年

    DOI： 10.48550/arXiv.2305.07262 　

  35. Happy Set Problem on Subclasses of Co-comparability Graphs 査読有り

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

    Algorithmica　85　(11)　3327-3347　2022年12月15日

    出版者・発行元： Springer Science and Business Media LLC

    DOI： 10.1007/s00453-022-01081-0 　

    ISSN：0178-4617

    eISSN：1432-0541

  36. Algorithms for coloring reconfiguration under recolorability digraphs 査読有り

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Akira Suzuki

    Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz International Proceedings in Informatics (LIPIcs)　248　4:1-4:19　2022年12月

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

    DOI： 10.4230/LIPIcs.ISAAC.2022.4 　

  37. Reconfiguring k-path vertex covers 査読有り

    Duc A. HOANG, Akira SUZUKI, Tsuyoshi YAGITA

    IEICE Transactions on Information and Systems　E105.D　(7)　1258-1272　2022年7月1日

    出版者・発行元： Institute of Electronics, Information and Communications Engineers (IEICE)

    DOI： 10.1587/transinf.2021edp7177 　

    ISSN：0916-8532

    eISSN：1745-1361

  38. Happy Set Problem on Subclasses of Co-comparability Graphs 査読有り

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

    Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), Lecture Notes in Computer Science (LNCS)　13174　149-160　2022年3月16日

    出版者・発行元： Springer International Publishing

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

    ISSN：0302-9743

    eISSN：1611-3349

  39. ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems.

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

    CoRR　abs/2207.13959　2022年

    DOI： 10.48550/arXiv.2207.13959 　

  40. 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

    CoRR　abs/2202.09495　2022年

    詳細を見る 詳細を閉じる

    Various forms of sorting problems have been studied over the years. Recently, two kinds of sorting puzzle apps are popularized. In these puzzles, we are given a set of bins filled with colored units, balls or water, and some empty bins. These puzzles allow us to move colored units from a bin to another when the colors involved match in some way or the target bin is empty. The goal of these puzzles is to sort all the color units in order. We investigate computational complexities of these puzzles. We first show that these two puzzles are essentially the same from the viewpoint of solvability. That is, an instance is sortable by ball-moves if and only if it is sortable by water-moves. We also show that every yes-instance has a solution of polynomial length, which implies that these puzzles belong to in NP. We then show that these puzzles are NP-complete. For some special cases, we give polynomial-time algorithms. We finally consider the number of empty bins sufficient for making all instances solvable and give non-trivial upper and lower bounds in terms of the number of filled bins and the capacity of bins.

  41. Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint.

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

    CoRR　abs/2201.04354　2022年

  42. Path Cover Problems with Length Cost. 査読有り

    Kenya Kobayashi, Guohui Lin, Eiji Miyano, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, Tsuyoshi Yagita

    Proceedings of the 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), Lecture Notes in Computer Science (LNCS)　13174　396-408　2022年

    出版者・発行元： Springer

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

  43. Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint 査読有り

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

    Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Leibniz International Proceedings in Informatics (LIPIcs)　219　15:1-15:21　2022年

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

    DOI： 10.4230/LIPIcs.STACS.2022.15 　

  44. 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

    Proceedings of the 11th International Conference on Fun with Algorithms (FUN 2022), Leibniz International Proceedings in Informatics (LIPIcs)　226　16:1-16:17　2022年

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

    DOI： 10.4230/LIPIcs.FUN.2022.16 　

  45. Decremental Optimization of Vertex-Coloring Under the Reconfiguration Framework 査読有り

    Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

    Proceedings of the 27th International Computing and Combinatorics Conference (COCOON 2021), Lecture Notes in Computer Science (LNCS)　13025　355-366　2021年10月20日

    出版者・発行元： Springer International Publishing

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

    ISSN：0302-9743

    eISSN：1611-3349

  46. Trichotomy for the reconfiguration problem of integer linear systems 査読有り

    Kei Kimura, Akira Suzuki

    Theoretical Computer Science　856　88-109　2021年2月

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.tcs.2020.12.025 　

    ISSN：0304-3975

  47. Max-Min 3-Dispersion Problems. 査読有り

    Takashi Horiyama, Shin-Ichi Nakano, Toshiki Saitoh, Koki Suetsugu, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences　104-A　(9)　1101-1107　2021年

    DOI： 10.1587/transfun.2020dmp0003 　

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

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

    Theoretical Computer Science　838　45-57　2020年10月

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.tcs.2020.05.033 　

    ISSN：0304-3975

  49. 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月

    出版者・発行元： Elsevier BV

    DOI： 10.1016/j.dam.2020.01.022 　

    ISSN：0166-218X

  50. 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　2020年8月29日

    出版者・発行元： Springer Science and Business Media LLC

    DOI： 10.1007/s10878-020-00630-z 　

    ISSN：1382-6905

    eISSN：1573-2886

  51. Decremental Optimization of Dominating Sets Under the Reconfiguration Framework 査読有り

    Alexandre Blanché, Haruka Mizuta, Paul Ouvrard, Akira Suzuki

    Proceedings of the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020), Lecture Notes in Computer Science (LNCS)　12126　69-82　2020年5月29日

    出版者・発行元： Springer International Publishing

    DOI： 10.1007/978-3-030-48966-3_6 　

    ISSN：0302-9743

    eISSN：1611-3349

  52. Shortest reconfiguration of colorings under kempe changes 査読有り

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

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

    出版者・発行元： Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

    DOI： 10.4230/LIPIcs.STACS.2020.35 　

    ISSN：1868-8969

  53. Reconfiguring k-path Vertex Covers 査読有り

    Duc A. Hoang, Akira Suzuki, Tsuyoshi Yagita

    Proceedings of the 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), Lecture Notes in Computer Science (LNCS)　12049　133-145　2020年2月20日

    出版者・発行元： Springer International Publishing

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

    ISSN：0302-9743

    eISSN：1611-3349

  54. Trichotomy for the Reconfiguration Problem of Integer Linear Systems 査読有り

    Kei Kimura, Akira Suzuki

    Proceedings of the 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020), Lecture Notes in Computer Science (LNCS)　12049　336-341　2020年2月20日

    出版者・発行元： Springer International Publishing

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

    ISSN：0302-9743

    eISSN：1611-3349

  55. 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 　

  56. Fixed-Parameter Algorithms for Graph Constraint Logic.

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

    CoRR　abs/2011.10385　2020年

    詳細を見る 詳細を閉じる

    Non-deterministic constraint logic (NCL) is a simple model of computation based on orientations of a constraint graph with edge weights and vertex demands. NCL captures \PSPACE\xspace and has been a useful tool for proving algorithmic hardness of many puzzles, games, and reconfiguration problems. In particular, its usefulness stems from the fact that it remains \PSPACE-complete even under severe restrictions of the weights (e.g., only edge-weights one and two are needed) and the structure of the constraint graph (e.g., planar \textsc{and/or}\xspace graphs of bounded bandwidth). While such restrictions on the structure of constraint graphs do not seem to limit the expressiveness of NCL, the building blocks of the constraint graphs cannot be limited without losing expressiveness: We consider as parameters the number of weight-one edges and the number of weight-two edges of a constraint graph, as well as the number of \textsc{and}\xspace or \textsc{or}\xspace vertices of an \textsc{and/or}\xspace constraint graph. We show that NCL is fixed-parameter tractable (FPT) for any of these parameters. In particular, for NCL parameterized by the number of weight-one edges or the number of \textsc{and}\xspace vertices, we obtain a linear kernel. It follows that, in a sense, NCL as introduced by Hearn and Demaine is defined in the most economical way for the purpose of capturing \PSPACE.

  57. Reconfiguration of Spanning Trees with Many or Few Leaves.

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

    CoRR　abs/2006.14309　2020年

    詳細を見る 詳細を閉じる

    Let $G$ be a graph and $T_1,T_2$ be two spanning trees of $G$. We say that $T_1$ can be transformed into $T_2$ via an edge flip if there exist two edges $e \in T_1$ and $f$ in $T_2$ such that $T_2= (T_1 \setminus e) \cup f$. Since spanning trees form a matroid, one can indeed transform a spanning tree into any other via a sequence of edge flips, as observed by Ito et al. We investigate the problem of determining, given two spanning trees $T_1,T_2$ with an additional property $\Pi$, if there exists an edge flip transformation from $T_1$ to $T_2$ keeping property $\Pi$ all along. First we show that determining if there exists a transformation from $T_1$ to $T_2$ such that all the trees of the sequence have at most $k$ (for any fixed $k \ge 3$) leaves is PSPACE-complete. We then prove that determining if there exists a transformation from $T_1$ to $T_2$ such that all the trees of the sequence have at least $k$ leaves (where $k$ is part of the input) is PSPACE-complete even restricted to split, bipartite or planar graphs. We complete this result by showing that the problem becomes polynomial for cographs, interval graphs and when $k=n-2$.

  58. Reconfiguration of Spanning Trees with Many or Few Leaves 査読有り

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

    Proceedings of the 28th Annual European Symposium on Algorithms (ESA 2020), Leibniz International Proceedings in Informatics (LIPIcs)　173　24:1-24:15　2020年

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

    DOI： 10.4230/LIPIcs.ESA.2020.24 　

  59. Fixed-Parameter Algorithms for Graph Constraint Logic 査読有り

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

    Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), Leibniz International Proceedings in Informatics (LIPIcs)　180　15:1-15:15　2020年

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

    DOI： 10.4230/LIPIcs.IPEC.2020.15 　

  60. Reconfiguring k-path vertex covers.

    Duc A. Hoang, Akira Suzuki, Tsuyoshi Yagita

    CoRR　abs/1911.03026　2019年

  61. Trichotomy for the reconfiguration problem of integer linear systems.

    Kei Kimura, Akira Suzuki

    CoRR　abs/1911.02786　2019年

    詳細を見る 詳細を閉じる

    In this paper, we consider the reconfiguration problem of integer linear systems. In this problem, we are given an integer linear system $I$ and two feasible solutions $\boldsymbol{s}$ and $\boldsymbol{t}$ of $I$, and then asked to transform $\boldsymbol{s}$ to $\boldsymbol{t}$ by changing a value of only one variable at a time, while maintaining a feasible solution of $I$ throughout. $Z(I)$ for $I$ is the complexity index introduced by Kimura and Makino (Discrete Applied Mathematics 200:67--78, 2016), which is defined by the sign pattern of the input matrix. We analyze the complexity of the reconfiguration problem of integer linear systems based on the complexity index $Z(I)$ of given $I$. We then show that the problem is (i) solvable in constant time if $Z(I)$ is less than one, (ii) weakly coNP-complete and pseudo-polynomially solvable if $Z(I)$ is exactly one, and (iii) PSPACE-complete if $Z(I)$ is greater than one. Since the complexity indices of Horn and two-variable-par-inequality integer linear systems are at most one, our results imply that the reconfiguration of these systems are in coNP and pseudo-polynomially solvable. Moreover, this is the first result that reveals coNP-completeness for a reconfiguration problem, to the best of our knowledge.

  62. Decremental Optimization of Dominating Sets Under Reachability Constraints.

    Alexandre Blanché, Haruka Mizuta, Paul Ouvrard, Akira Suzuki

    CoRR　abs/1906.05163　2019年

  63. 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年

    出版者・発行元： Springer

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

  64. Sequentially Swapping Colored Tokens on Graphs. 査読有り

    Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-Ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno

    J. Graph Algorithms Appl.　23　(1)　3-27　2019年

    DOI： 10.7155/jgaa.00482 　

  65. Diameter of Colorings Under Kempe Changes. 査読有り

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

    Computing and Combinatorics - 25th International Conference, COCOON 2019, Xi'an, China, July 29-31, 2019, Proceedings　52-64　2019年

    出版者・発行元： Springer

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

  66. Max-Min 3-Dispersion Problems. 査読有り

    Takashi Horiyama, Shin-Ichi Nakano, Toshiki Saitoh, Koki Suetsugu, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa

    Computing and Combinatorics - 25th International Conference, COCOON 2019, Xi'an, China, July 29-31, 2019, Proceedings　291-300　2019年

    出版者・発行元： Springer

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

  67. Computational Power of Threshold Circuits of Energy at most Two 査読有り

    Hiroki MANIWA, Takayuki OKI, Akira SUZUKI, Kei UCHIZAWA, Xiao ZHOU

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences　E101.A　(9)　1431-1439　2018年9月1日

    出版者・発行元： Institute of Electronics, Information and Communications Engineers (IEICE)

    DOI： 10.1587/transfun.e101.a.1431 　

    ISSN：0916-8508

    eISSN：1745-1337

  68. グラフの色付きトークン整列問題について (アルゴリズムと計算理論の基礎と応用)

    金野, 駿人, 鈴木, 顕, 山中, 克久, 伊藤, 健洋, 周, 暁

    数理解析研究所講究録　2088　53-62　2018年8月

    出版者・発行元： 京都大学数理解析研究所

    ISSN：1880-2818

  69. Reconfiguring spanning and induced subgraphs.

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

    CoRR　abs/1803.06074　2018年

  70. Incremental Optimization of Independent Sets under Reachability Constraints.

    Takehiro Ito, Haruka Mizuta, Naomi Nishimura, Akira Suzuki

    CoRR　abs/1804.09422　2018年

    詳細を見る 詳細を閉じる

    We introduce a new framework for reconfiguration problems, and apply it to independent sets as the first example. Suppose that we are given an independent set $I_0$ of a graph $G$, and an integer $l \ge 0$ which represents a lower bound on the size of any independent set of $G$. Then, we are asked to find an independent set of $G$ having the maximum size among independent sets that are reachable from $I_0$ by either adding or removing a single vertex at a time such that all intermediate independent sets are of size at least $l$. We show that this problem is PSPACE-hard even for bounded pathwidth graphs, and remains NP-hard for planar graphs. On the other hand, we give a linear-time algorithm to solve the problem for chordal graphs. We also study the fixed-parameter (in)tractability of the problem with respect to the following three parameters: the degeneracy $d$ of an input graph, a lower bound $l$ on the size of the independent sets, and a lower bound $s$ on the solution size. We show that the problem is fixed-parameter intractable when only one of $d$, $l$, and $s$ is taken as a parameter. On the other hand, we give a fixed-parameter algorithm when parameterized by $s+d$; this result implies that the problem parameterized only by $s$ is fixed-parameter tractable for planar graphs, and for bounded treewidth graphs.

  71. 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年

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

    DOI： 10.4230/LIPIcs.ISAAC.2018.37 　

  72. 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　abs/1803.06074　428-440　2018年

    出版者・発行元：

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

  73. The complexity of (List) edge-coloring reconfiguration problem 査読有り

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences　E101A　(1)　232-238　2018年1月1日

    出版者・発行元： Institute of Electronics, Information and Communication, Engineers, IEICE

    DOI： 10.1587/transfun.E101.A.232 　

    ISSN：1745-1337 0916-8508

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

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    Leibniz International Proceedings in Informatics, LIPIcs　92　62:1-62:12　2017年12月1日

    出版者・発行元： Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

    DOI： 10.4230/LIPIcs.ISAAC.2017.62 　

    ISSN：1868-8969

  75. 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年10月

    DOI： 10.1007/s00454-017-9884-9 　

    ISSN：0179-5376

    eISSN：1432-0444

  76. Complexity of "Goishi Hiroi" 査読有り

    Masanori Fukui, Koki Suetsugu, Akira Suzuki

    The 20th Anniversary of Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2017)　2017年9月1日

  77. Hitori numbers 査読有り

    Akira Suzuki, Masashi Kiyomi, Yota Otachi, Kei Uchizawa, Takeaki Uno

    Journal of Information Processing　25　695-707　2017年8月1日

    出版者・発行元： Information Processing Society of Japan

    DOI： 10.2197/ipsjjip.25.695 　

    ISSN：1882-6652 0387-5806

  78. On the Parameterized Complexity of Reconfiguration Problems 査読有り

    Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour, Akira Suzuki

    ALGORITHMICA　78　(1)　274-297　2017年5月

    DOI： 10.1007/s00453-016-0159-2 　

    ISSN：0178-4617

    eISSN：1432-0541

  79. The Complexity of (List) Edge-Coloring Reconfiguration Problem 査読有り

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017　10167　347-358　2017年

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

    ISSN：0302-9743

    eISSN：1611-3349

  80. Sequentially Swapping Colored Tokens on Graphs 査読有り

    Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno

    WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017　10167　435-447　2017年

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

    ISSN：0302-9743

    eISSN：1611-3349

  81. Reconfiguration of dominating sets 招待有り 査読有り

    Akira Suzuki, Amer E. Mouawad, Naomi Nishimura

    JOURNAL OF COMBINATORIAL OPTIMIZATION　32　(4)　1182-1195　2016年11月

    DOI： 10.1007/s10878-015-9947-x 　

    ISSN：1382-6905

    eISSN：1573-2886

  82. The multi-service center decision problem is NP-complete for split graphs 査読有り

    Toshimitsu Anzai, Takehiro Ito, Akira Suzuki, Xiao Zhou

    Proceedings of the 2016 International Conference on Applied and Engineering Mathematics (AEM 2016)　2016年10月23日

  83. 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　(C)　37-49　2016年10月

    DOI： 10.1016/j.tcs.2016.08.016 　

    ISSN：0304-3975

    eISSN：1879-2294

  84. Computational Complexity of Sequential Token Swapping Problem (コンピュテーション)

    山中 克久, ドメイン エリック, 堀山 貴史, 河村 彰星, 中野 眞一, 岡本 吉央, 斎藤 寿樹, 鈴木 顕, 上原 隆平, 宇野 毅明

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報　116　(116)　115-121　2016年6月24日

    出版者・発行元： 電子情報通信学会

    ISSN：0913-5685

  85. シーケンシャルな交換による色付きトークン整列問題の計算複雑さ

    山中 克久, エリック ドメイン, 堀山 貴史, 河村 彰星, 中野 眞一, 岡本 吉央, 斎藤 寿樹, 鈴木 顕, 上原 隆平, 宇野 毅明

    第158回アルゴリズム研究会　1-7　2016年6月

  86. The Complexity of (List) Edge-Coloring Reconfiguration Problem.

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou 0001

    CoRR　abs/1609.00109　2016年

  87. 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年6月

    DOI： 10.1016/j.tcs.2015.01.052 　

    ISSN：0304-3975

    eISSN：1879-2294

  88. 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 (IIS)　21　(1)　25-36　2015年3月20日

    出版者・発行元： 東北大学

    DOI： 10.4036/iis.2015.25 　

    ISSN：1340-9050

    詳細を見る 詳細を閉じる

    For a digraph G = (V,A) and a source vertex s ∈ V, suppose that we wish to compute a shortest directed path from s to every vertex v ∈ V \ {s} (if exists) under several arc costs. Frigioni et al. (2000) proposed a dynamic algorithm which efficiently reuses the shortest-paths information computed for the previous arc costs. In this paper, we experimentally evaluate how such a dynamic algorithm works efficiently for real-world networks.

  89. The complexity of dominating set reconfiguration.

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

    CoRR　abs/1503.00833　2015年

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

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

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　9214　398-409　2015年

    出版者・発行元： Springer Verlag

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

    ISSN：1611-3349 0302-9743

  91. Competitive diffusion on weighted graphs 査読有り

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

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　9214　422-433　2015年

    出版者・発行元： Springer Verlag

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

    ISSN：1611-3349 0302-9743

  92. グラフ上のラベル付きトークン整列問題

    山中 克久, エリック, ドメイン(MIT, 伊藤 健洋, 川原純, 清見 礼, 岡本 吉央, 斎藤 寿樹, 鈴木 顕, 内澤 啓, 宇野 毅明(N

    電子情報通信学会コンピュテーション研究会資料　2014　(2)　5-12　2014年4月

  93. On the Minimum Caterpillar Problem in Digraphs 査読有り

    Taku Okada, Akira Suzuki, Takehiro Ito, Xiao Zhou

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES　E97A　(3)　848-857　2014年3月

    DOI： 10.1587/transfun.E97.A.848 　

    ISSN：0916-8508

    eISSN：1745-1337

  94. Reconfiguration of Dominating Sets.

    Akira Suzuki, Amer E. Mouawad, Naomi Nishimura

    CoRR　abs/1401.5714　2014年

  95. Computational Complexity of Competitive Diffusion on (Un)weighted Graphs.

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

    CoRR　abs/1412.3334　2014年

    詳細を見る 詳細を閉じる

    Consider an undirected graph modeling a social network, where the vertices represent users, and the edges do connections among them. In the competitive diffusion game, each of a number of players chooses a vertex as a seed to propagate his/her opinion, and then it spreads along the edges in the graphs. The objective of every player is to maximize the number of vertices the opinion infects. In this paper, we investigate a computational problem of asking whether a pure Nash equilibrium exists in the competitive diffusion game on unweighed and weighted graphs, and present several negative and positive results. We first prove that the problem is W[1]-hard when parameterized by the number of players even for unweighted graphs. We also show that the problem is NP-hard even for series-parallel graphs with positive integer weights, and is NP-hard even for forests with arbitrary integer weights. Furthermore, we show that the problem for forest of paths with arbitrary weights is solvable in pseudo-polynomial time; and it is solvable in quadratic time if a given graph is unweighted. We also prove that the problem for chain, cochain, and threshold graphs with arbitrary integer weights is solvable in polynomial time.

  96. On the Parameterized Complexity for Token Jumping on Graphs 査読有り

    Takehiro Ito, Marcin Kaminski, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, Katsuhisa Yamanaka

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION (TAMC 2014)　8402　341-351　2014年

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

    ISSN：0302-9743

  97. 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　8496　364-375　2014年

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

    ISSN：0302-9743

  98. Reconfiguration of Dominating Sets 査読有り

    Akira Suzuki, Amer E. Mouawad, Naomi Nishimura

    COMPUTING AND COMBINATORICS, COCOON 2014　8591　405-416　2014年

    DOI： 10.1007/978-3-319-08783-2_35 　

    ISSN：0302-9743

  99. 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年10月

    DOI： 10.1007/s00453-012-9689-4 　

    ISSN：0178-4617

  100. Energy and fan-in of logic circuits computing symmetric Boolean functions 招待有り 査読有り

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    THEORETICAL COMPUTER SCIENCE　505　74-80　2013年9月

    DOI： 10.1016/j.tcs.2012.11.039 　

    ISSN：0304-3975

    eISSN：1879-2294

  101. Energy-efficient threshold circuits detecting global pattern in 1-dimensional arrays 査読有り

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    Proceedings of the 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2013)　17-17　2013年4月20日

  102. Algorithm for the minimum caterpillar problem with terminals 査読有り

    Taku Okada, Akira Suzuki, Takehiro Ito, Xiao Zhou

    Proceedings of the 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2013)　25-25　2013年4月20日

  103. On the Parameterized Complexity of Reconfiguration Problems.

    Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman 0001, Narges Simjour, Akira Suzuki

    CoRR　abs/1308.2409　2013年

  104. ENERGY-EFFICIENT THRESHOLD CIRCUITS COMPUTING MOD FUNCTIONS 招待有り 査読有り

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE　24　(1)　15-29　2013年1月

    DOI： 10.1142/S0129054113400029 　

    ISSN：0129-0541

  105. Energy-efficient threshold circuits detecting global pattern in 1-dimentional arrays 査読有り

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　7876　248-259　2013年

    出版者・発行元： Springer Verlag

    DOI： 10.1007/978-3-642-38236-9_23 　

    ISSN：1611-3349 0302-9743

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

    Taku Okada, Akira Suzuki, Takehiro Ito, Xiao Zhou

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　7936　729-736　2013年

    出版者・発行元： Springer

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

    ISSN：0302-9743 1611-3349

  107. On the parameterized complexity of reconfiguration problems 査読有り

    Amer E. Mouawad, Naomi Nishimura, Venkatesh Raman, Narges Simjour, Akira Suzuki

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　8246　281-294　2013年

    出版者・発行元： Springer

    DOI： 10.1007/978-3-319-03898-8_24 　

    ISSN：0302-9743 1611-3349

  108. トロミノ詰込問題の計算複雑さについて

    堀山 貴史, 伊藤 健洋, 中束 渓太, 鈴木 顕, 上原 隆平

    電子情報通信学会技術研究報告. COMP, コンピュテーション　112　(272)　37-43　2012年10月24日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN：0913-5685

    詳細を見る 詳細を閉じる

    与えられた盤面に1種類のポリオミノを詰め込む問題に対し,その計算複雑さを研究する.ドミノ(すなわち.1×2の矩形)を詰め込む問題は,二部グラフのマッチング問題に帰着することで,多項式時間で解けることが知られている.一方で,2×2の正方形を詰め込む問題は,NP完全であることが知られている.本論文では,トロミノ(すなわち,サイズ3のポリオミノ)を詰め込む問題を扱うことで,これら既存研究のギャップを埋める.ここで,トロミノはL型とI型の2種類が存在することに注意が必要である.本論文では,どちらのトロミノを詰め込む問題もNP完全であることを示す.また,これらの帰着を注意深く設計することで,トロミノ詰込問題の数え上げ版が#P完全であり,別解問題版がASP完全であることを示す.

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

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

    Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012)　219-224　2012年8月9日

  110. 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年

  111. Hitori number 査読有り

    Akira Suzuki, Kei Uchizawa, Takeaki Uno

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　7288　334-345　2012年

    出版者・発行元： Springer

    DOI： 10.1007/978-3-642-30347-0_33 　

    ISSN：0302-9743 1611-3349

  112. Energy-efficient threshold circuits computing Mod functions 査読有り

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    Proceedings of the 17th Computing: the Australasian Theory Symposium (CATS 2011), Conferences in Research and Practice in Information Technology (CRPIT)　119　105-110　2011年1月20日

    出版者・発行元：

  113. Energy and Fan-In of Threshold Circuits Computing Mod Functions 査読有り

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011　6648　154-163　2011年

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

    ISSN：0302-9743

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

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

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)　6842　86-97　2011年

    出版者・発行元： Springer

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

    ISSN：0302-9743 1611-3349

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

MISC 31

  1. グラフ構造を用いたメンバーシップ支配集合問題の計算複雑性に関する研究

    若山大智, 鈴木顕, 田村祐馬, 周暁

    情報処理学会研究報告(Web)　2025　(AL-203)　2025年

  2. 拡張ルールの下での独立集合および頂点被覆再構成【JST機械翻訳】|||

    HIRAHARA Shuichi, OHSAKA Naoto, SUGA Tatsuhiro, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

    情報処理学会研究報告(Web)　2025　(AL-203)　2025年

  3. 緩和制約による最短経路再構成

    DOMON Naoki, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

    情報処理学会研究報告(Web)　2024　(AL-196)　2024年

  4. 重み付きターゲット集合選択のためのアルゴリズム【JST機械翻訳】

    SUZUKI Takahiro, KIMURA Kei, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

    電子情報通信学会大会講演論文集(CD-ROM)　2024　2024年

    ISSN： 1349-144X

  5. 遷移ルールの緩和に基づく独立集合遷移問題

    菅達皓, 鈴木顕, 田村祐馬, ZHOU Xiao

    電子情報通信学会大会講演論文集(CD-ROM)　2024　2024年

    ISSN： 1349-144X

  6. 組合せ遷移問題を扱うソフトウェアについて

    伊藤健洋, 川原純, 中畑裕, 宋剛秀, 鈴木顕, 照山順一, 戸田貴久

    情報処理学会研究報告(Web)　2024　(AL-200)　2024年

  7. 事故復旧を考慮した配電系統構成の最適化に関する検討—A Study on Optimizing Configurations of Distribution Networks for Service Restoration—電力技術/電力系統技術合同研究会 (1)電力技術・電力系統技術一般 (2)分散電源・次世代グリッド・系統セキュリティ

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

    電気学会研究会資料. PSE = The papers of Technical Meeting on "Power Systems Engineering", IEE Japan / 電力系統技術研究会 [編]　2023　(135-137・139-145・149・204-209・211-218)　7-12　2023年9月

    出版者・発行元： 東京 : 電気学会

  8. 事故復旧を考慮した配電系統構成の最適化に関する検討—A Study on Optimizing Configurations of Distribution Networks for Service Restoration—電力技術/電力系統技術合同研究会・(1)電力技術・電力系統技術一般 (2)分散電源・次世代グリッド・系統セキュリティ

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

    電気学会研究会資料. PE / 電気学会電力技術研究会 [編]　2023　(143-145・147-153・157・212-217・219-226)　7-12　2023年9月

    出版者・発行元： 東京 : 電気学会

  9. グラフ構造に基づく順序付き禁則遷移を回避する経路探索の問題について

    KUMAKURA Kota, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

    情報処理学会研究報告(Web)　2023　(AL-195)　2023年

  10. 配電損失最小化問題に対する組合せ遷移的アプローチ

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

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集　2022　2022年

    ISSN： 1883-1893

  11. 区間グラフに対するハミルトン閉路遷移問題

    佐藤颯介, 鈴木顕, 伊藤健洋, ZHOU Xiao

    電子情報通信学会大会講演論文集(CD-ROM)　2021　2021年

    ISSN： 1349-144X

  12. 頂点色付け再構成問題に関する最適化バリアント

    YANAGISAWA Yusuke, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

    情報処理学会研究報告(Web)　2021　(AL-185)　2021年

  13. 放射状系統作成による配電損失最小化手法と切替手順の算出手法—Method for Distribution Loss Minimization and Switching Operation Procedures with Radial Network Reconfiguration—電力技術 電力系統技術合同研究会 (1)電力技術・電力系統技術一般,(2)分散電源・次世代グリッド

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

    電気学会研究会資料. PSE = The papers of Technical Meeting on "Power Systems Engineering", IEE Japan / 電力系統技術研究会 [編]　2019　(91-103・156・158-169)　25-29　2019年9月

    出版者・発行元： 東京 : 電気学会

  14. グラフ上の経路固定サーバ割当問題のパラメータ複雑性

    岩本裕二, 水田遥河, 鈴木顕, 伊藤健洋, ZHOU Xiao

    情報処理学会全国大会講演論文集　81st　(1)　2019年

  15. グラフ上のパケットルーティング問題のパラメータ複雑性に関する研究

    菊池正太, 鈴木顕, 伊藤健洋, ZHOU Xiao

    情報処理学会全国大会講演論文集　81st　(1)　2019年

  16. 放射状系統作成による配電損失最小化手法と切替手順の算出手法

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

    電気学会研究会資料　(PE-19-079-157/PSE-19-091-169)　2019年

  17. 一般化彩色遷移問題に対する線形時間アルゴリズム

    OSAWA Hiroki, SUZUKI Akira, ITO Takehiro, ZHOU Xiao

    電子情報通信学会技術研究報告　118　(356(COMP2018 31-42)(Web))　2018年

    ISSN： 0913-5685

  18. Complexity of Coloring Reconfiguration under Recolorability Constraints (システム数理と応用)

    OSASA HIROKI, SUZUKI AKIRA, ITO TAKEHIRO, ZHOU XIAO

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報　117　(301)　29-35　2017年11月16日

    出版者・発行元： 電子情報通信学会

    ISSN： 0913-5685

  19. Hitori Numbers

    Akira Suzuki, Masashi Kiyomi, Yota Otachi, Kei Uchizawa, Takeaki Uno

    情報処理学会論文誌　58　(8)　2017年8月15日

    ISSN： 1882-7764

    詳細を見る 詳細を閉じる

    Hitori is a popular "pencil-and-paper" puzzle defined as follows. In n-hitori, we are given an n × n rectangular grid in which each square is labeled with a positive integer, and the goal is to paint a subset of the squares so that the following three rules are satisfied: Rule 1) No row or column has a repeated unpainted label; Rule 2) Painted squares are never (horizontally or vertically) adjacent; Rule 3) The unpainted squares are all connected (via horizontal and vertical connections). The grid is called an instance of n-hitori if it has a unique solution. In this paper, we introduce hitori number and maximum hitori numberwhich are defined as follows: For every integer n, hitori number h(n) is the minimum number of different integers used in an instance where the minimum is taken over all the instances of n-hitori. For every integer n, maximum hitori number $\bar{h}(n)$ is the maximum number of different integers used in an instance where the maximum is taken over all the instances of n-hitori. We then prove that ⎾(2n-1)/3⏋ ≤ h(n) ≤ 2⎾n/3⏋+1 for n ≥ 2 and ⎾(4n2-4n+11)/5⏋ ≤ $\bar{h}(n)$ ≤ (4n2+2n-2)/5 for n ≥ 3.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.695------------------------------Hitori is a popular "pencil-and-paper" puzzle defined as follows. In n-hitori, we are given an n × n rectangular grid in which each square is labeled with a positive integer, and the goal is to paint a subset of the squares so that the following three rules are satisfied: Rule 1) No row or column has a repeated unpainted label; Rule 2) Painted squares are never (horizontally or vertically) adjacent; Rule 3) The unpainted squares are all connected (via horizontal and vertical connections). The grid is called an instance of n-hitori if it has a unique solution. In this paper, we introduce hitori number and maximum hitori numberwhich are defined as follows: For every integer n, hitori number h(n) is the minimum number of different integers used in an instance where the minimum is taken over all the instances of n-hitori. For every integer n, maximum hitori number $\bar{h}(n)$ is the maximum number of different integers used in an instance where the maximum is taken over all the instances of n-hitori. We then prove that ⎾(2n-1)/3⏋ ≤ h(n) ≤ 2⎾n/3⏋+1 for n ≥ 2 and ⎾(4n2-4n+11)/5⏋ ≤ $\bar{h}(n)$ ≤ (4n2+2n-2)/5 for n ≥ 3.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.695------------------------------

  20. Energy-efficient Threshold Circuits Computing Generalized Symmetric Functions (理論計算機科学の最先端)

    Maniwa Hiroki, Oki Takayuki, Suzuki Akira, Uchizawa Kei, Zhou Xiao

    数理解析研究所講究録　(2040)　21-26　2017年7月

    出版者・発行元： 京都大学数理解析研究所

    ISSN： 1880-2818

  21. 汎用彩色再構成の問題のためのアルゴリズム

    OSAWA Hiroki, SUZUKI Akira, SUZUKI Akira, ITO Takehiro, ITO Takehiro, ZHOU Xiao

    情報処理学会研究報告(Web)　2016　(AL-156)　2016年

  22. FPT Algorithms for Token Jumping on Graphs (コンピュテーション)

    ITO TAKEHIRO, KAMINSKI MARCIN, ONO HIROTAKA, SUZUKI AKIRA, UEHARA RYUHEI, YAMANAKA KATSUHISA

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報　114　(80)　9-12　2014年6月13日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    Suppose that we are given two independent sets I_0 and I_r of a graph such that |I_0| = |I_r|, and imagine that a token is placed on each vertex in I_0. Then, the TOKEN JUMPING problem is to determine whether there exists a sequence of independent sets which transforms I_0 into I_r so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. Therefore, all independent sets in the sequence must be of the same cardinality. This problem is W[1]-hard when parameterized only by the number of tokens. In this paper, we give FPT algorithms for general graphs when parameterized by both the number of tokens and the maximum degree.

  23. FPT algorithms for Token Jumping on Graphs

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

    研究報告アルゴリズム（AL）　2014　(2)　1-4　2014年6月6日

    出版者・発行元： 一般社団法人情報処理学会

    ISSN： 0919-6072

    詳細を見る 詳細を閉じる

    Suppose that we are given two independent sets I0 and Ir of a graph such that |I0| = |Ir|, and imagine that a token is placed on each vertex in I0. Then, the token jumping problem is to determine whether there exists a sequence of independent sets which transforms I0 into Ir so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. Therefore, all independent sets in the sequence must be of the same cardinality. This problem is W[1]-hard when parameterized only by the number of tokens. In this paper, we give FPT algorithms for general graphs when parameterized by both the number of tokens and the maximum degree.Suppose that we are given two independent sets I0 and Ir of a graph such that |I0| = |Ir|, and imagine that a token is placed on each vertex in I0. Then, the token jumping problem is to determine whether there exists a sequence of independent sets which transforms I0 into Ir so that each independent set in the sequence results from the previous one by moving exactly one token to another vertex. Therefore, all independent sets in the sequence must be of the same cardinality. This problem is W[1]-hard when parameterized only by the number of tokens. In this paper, we give FPT algorithms for general graphs when parameterized by both the number of tokens and the maximum degree.

  24. グラフの経路固定サーバ割当問題に関する研究 (計算理論とアルゴリズムの新潮流)

    大日野 肇, 伊藤 健洋, 鈴木 顕, 内澤 啓, 周 暁

    数理解析研究所講究録　1894　41-44　2014年5月

    出版者・発行元： 京都大学

    ISSN： 1880-2818

  25. 支配集合の遷移可能性

    鈴木 顕, Mouawad Amer E., NaomiNishimura

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報　114　(19)　29-35　2014年4月24日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    本論文では支配集合の遷移可能性問題を扱う.支配集合とは,グラフGの点集合の部分集合Sのうち,Gの各点がSに含まれるかSと隣接しているものをいう.支配集合の遷移可能性問題とは,あるグラフに対する2つの支配集合が与えられ,それらを繋ぐ支配集合の列が存在するか判定する問題である.ただし,列内の支配集合同士が隣接するためには,隣接条件を満たさなければならない.本論文では,一方の支配集合に対して点を1つ加えるか取り除くことでもう一方の支配集合が得られるときに,2つの支配集合は隣接すると定義した.ある整数kに対して,点集合が高々k点からなるグラフGの支配集合の集合であり,隣接条件を満たす支配集合同士に辺を引いたグラフD_k(G)を考える.我々は2013年にHaasとSeyffarthによって立てられた,D_<Γ(G)+1>(G)は常に連結であるという予想に対する反例を与えた.ここでΓ(G)とはGの極小支配集合の点数の最大値である.我々の反例は,グラフクラスを平面グラフ,木幅制限グラフ,b部グラフ,b≧3,に制限しても成り立つ.さらに我々は,D_<γ(G)+1>(G)の直径が指数長になるようなグラフの族を与えた.ここで_γ(G)とはGの最小支配集合の点数である.一方で我々は,n点からなるグラフGが少なくともm+1本の互いに素な辺を持っていれば,D_<n-m>(G)は常に連結であり,その直径はnに対する線形長であることを示した.

  26. Energy-Efficient Threshold Circuits Detecting Global Pattern in 1-Dimensional Arrays (New Trends in Theoretical Computer Science)

    鈴木 顕, 内澤 啓, 周 暁

    数理解析研究所講究録　1849　133-134　2013年8月

    出版者・発行元： 京都大学

  27. DS-1-5 ひとりにしてくれ数(DS-1.COMP学生シンポジウム,シンポジウムセッション)

    鈴木 顕, 内澤 啓, 宇野 毅明

    電子情報通信学会総合大会講演論文集　2012　(1)　"S-9"-"S-10"　2012年3月6日

    出版者・発行元： 一般社団法人電子情報通信学会

    詳細を見る 詳細を閉じる

    Hitori is a popular "pencil-and-paper" puzzle game. In n-hitori, we are given an n×n rectangular grid of which each square is labeled with a positive integer, and the goal is to paint a subset of the squares so that the following three rules hold: Rule 1) No row or column has a repeated unpainted label; Rule 2) Painted squares are never (horizontally or vertically) adjacent; Rule 3) The unpainted squares are all connected (via horizontal and vertical connections.) The grid is called an instance of n-hitori if it has an unique solution. In this paper, we introduce hitori number defined as follows: For every integer n &ge; 2, hitori number h(n) is the minimum number of different integers used in an instance where the minimum is taken over all the instances of n-hitori. We then prove that [(2n-1)/3] &le; h(n) &ge; 2[n/31+1.

  28. DS-1-4 剰余関数を計算するしきい値回路のエネルギー複雑度とファンイン(DS-1.COMP学生シンポジウム,シンポジウムセッション)

    鈴木 顕, 内澤 啓, 周 暁

    電子情報通信学会総合大会講演論文集　2011　(1)　"S-7"-"S-8"　2011年2月28日

    出版者・発行元： 一般社団法人電子情報通信学会

    詳細を見る 詳細を閉じる

    We consider a threshold circuit C computing the modulus function MOD_m, and investigate a relationship between energy e and fan-in l of C, where the energy e is defined to be the maximum number of gates outputting "1" over all inputs to C, and the fan-in l to be the maximum number of inputs of every gate in C. We first prove that MOD_m of n variables can be computed by a threshold circuit of energy e=O(n/l) and fan-in l, and then show that the upper bound on the energy e is almost tight by providing a lower bound e=Ω((n-m)/l). Our results imply that there exists a tradeoff between the energy and fan-in of threshold circuits computing the modulus function.

  29. Hardness and FPT Algorithm for the Rainbow Connectivity of Graphs (アルゴリズム(AL) Vol.2011-AL-134)

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

    研究報告アルゴリズム（AL）　2011　(4)　1-8　2011年2月28日

    出版者・発行元： 情報処理学会

    ISSN： 2186-2583

    詳細を見る 詳細を閉じる

    For a graph G = (V,E) and a color set C, let f : E → C be an edge-coloring of G which is not necessarily proper. Then, the graph G edge-colored by f is rainbow connected if every two vertices of G has a path in which all edges are assigned distinct colors by f. In this paper, we give three results for the problem of determining whether the graph colored by a given edge-coloring is rainbow connected. The first is to show that the problem is strongly NP-complete even for outerplanar graphs. We also show that the problem is strongly NP-complete for graphs of diameter 2. In contrast, as the second result, we show that the problem can be solved in polynomial time for cacti. Notice that both outerplanar graphs and cacti are of treewidth 2, and hence our complexity analysis is precise in some sense. The third is to give an FPT algorithm for general graphs when parameterized by the number of colors in C; this result implies that the problem can be solved in polynomial time for general graphs with n vertices if |C| = O(log n).For a graph G = (V,E) and a color set C, let f : E → C be an edge-coloring of G which is not necessarily proper. Then, the graph G edge-colored by f is rainbow connected if every two vertices of G has a path in which all edges are assigned distinct colors by f. In this paper, we give three results for the problem of determining whether the graph colored by a given edge-coloring is rainbow connected. The first is to show that the problem is strongly NP-complete even for outerplanar graphs. We also show that the problem is strongly NP-complete for graphs of diameter 2. In contrast, as the second result, we show that the problem can be solved in polynomial time for cacti. Notice that both outerplanar graphs and cacti are of treewidth 2, and hence our complexity analysis is precise in some sense. The third is to give an FPT algorithm for general graphs when parameterized by the number of colors in C; this result implies that the problem can be solved in polynomial time for general graphs with n vertices if |C| = O(log n).

  30. グラフの虹接続性に対する困難性およびFPTアルゴリズム

    AOKI Takanori, ITO Takehiro, SUZUKI Akira, UCHIZAWA Kei, ZHOU Xiao

    情報処理学会研究報告(CD-ROM)　2010　(6)　2011年

    ISSN： 2186-2583

  31. 剰余関数を計算するエネルギー複雑度の小さいしきい値回路

    鈴木 顕, 内沢 啓, 周 暁

    電子情報通信学会技術研究報告. COMP, コンピュテーション　110　(325)　7-13　2010年11月26日

    出版者・発行元： 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    詳細を見る 詳細を閉じる

    本論文では,任意の整数e≧2について,n入力MOD_m関数が素子数s=O(e(n/m)^<1/(e-1)>)かつエネルギー複雑度eなるしきい値回路Cで計算できることを示す.ここで,eは"1"を出力する素子の最大数である,すなわち,Cは任意の入力に対して高々e個の素子しか"1"を出力しない.本論文で得られた素子数の上界は,これまで知られていた下界s=Ω(e(n/m)^<1/e>)とほぼ一致する.

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

書籍等出版物 1

  1. 機械学習アルゴリズム (探検データサイエンス)

    共立出版　2021年6月

講演・口頭発表等 37

  1. Fixed-parameter algorithms for graph constraint logic

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

    The 15th International Symposium on Parameterized and Exact Computation (IPEC 2020)　2020年12月16日

  2. Reconfiguration of spanning trees with many or few leaves

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

    The 28th Annual European Symposium on Algorithms (ESA 2020)　2020年9月7日

  3. Decremental optimization of dominating sets under the reconfiguration framework

    Alexandre Blanché, Paul Ouvrard, Haruka Mizuta, Akira Suzuki

    The 31st International Workshop on Combinatorial Algorithms (IWOCA 2020)　2020年6月10日

  4. Trichotomy for the reconfiguration problem of integer linear systems

    Kei Kimura, Akira Suzuki

    The 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020)　2020年4月2日

  5. Reconfiguring k-path vertex covers

    Duc A. Hoang, Akira Suzuki, Tsuyoshi Yagita

    The 14th International Conference and Workshops on Algorithms and Computation (WALCOM 2020)　2020年4月1日

  6. Shortest reconfiguration of colorings under Kempe-changes

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

    The 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)　2020年3月12日

  7. Optimizing dominating sets under constrained transformation

    Alexandre Blanché, Paul Ouvrard, Haruka Mizuta, Akira Suzuki

    The fifth Bordeaux Graph Workshop (BGW 2019)　2019年10月29日

  8. Diameter of colorings under Kempe changes

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

    The 25th International Computing and Combinatorics Conference (COCOON 2019)　2019年7月30日

  9. Max-Min 3-dispersion Problems

    Takashi Horiyama, Shin-Ichi Nakano, Toshiki Saitoh, Koki Suetsugu, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa

    The 25th International Computing and Combinatorics Conference (COCOON 2019)　2019年7月29日

  10. Incremental optimization of independent sets under the reconfiguration framework

    Takehiro Ito, Haruka Mizuta, Naomi Nishimura, Akira Suzuki

    The 25th International Computing and Combinatorics Conference (COCOON 2019)　2019年7月29日

  11. Optimizing independent sets under constrained transformation

    Takehiro Ito, Haruka Mizuta, Naomi Nishimura, Akira Suzuki

    The 11th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ 2019)　2019年5月29日

  12. Algorithms for coloring reconfiguration under recolorability constraints

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    The 29th International Symposium on Algorithms and Computation (ISAAC 2018)　2018年12月18日

  13. Reconfiguring spanning and induced subgraphs

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

    The 24th International Computing and Combinatorics Conference (COCOON 2018)　2018年7月3日

  14. Complexity of Coloring Reconfiguration under Recolorability Constraints 国際会議

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    The 28th International Symposium on Algorithms and Computation (ISAAC 2017)　2017年12月10日

  15. Computational power of energy-efficient threshold circuits 国際会議

    Akira Suzuki

    2017 Bilateral Workshop between Tohoku University and National Tsing Hua University　2017年10月13日

  16. Complexity of "Goishi Hiroi" 国際会議

    Masanori Fukui, Koki Suetsugu, Akira Suzuki

    The 20th Anniversary of Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2017)　2017年8月29日

  17. The complexity of (list) edge-coloring reconfiguration problem 国際会議

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    The 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017)　2017年3月29日

  18. Sequentially swapping colored tokens on graphs 国際会議

    Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-Ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno

    The 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017)　2017年3月29日

  19. Reduction tools on NCL 国際会議

    Akira Suzuki

    The Second International Workshop on Combinatorial Reconfiguration (CoRe 2017), Combinatorial Reconfiguration (17w5066)　2017年1月22日

  20. The multi-service center decision problem is NP-complete for split graphs 国際会議

    Toshimitsu Anzai, Takehiro Ito, Akira Suzuki, Xiao Zhou

    The 2016 International Conference on Applied and Engineering Mathematics (AEM 2016)　2016年10月21日

  21. The complexity of dominating set reconfiguration 国際会議

    The 14th Algorithms and Data Structures Symposium (WADS 2015)　2015年8月5日

  22. Competitive diffusion on weighted graphs 国際会議

    The 14th Algorithms and Data Structures Symposium (WADS 2015)　2015年8月5日

  23. Algorithms for maintaining shortest-paths trees on real-world networks 国際会議

    Data Science in Life Science and Engineering Collaboration and Symposium　2015年7月29日

  24. Reconfiguration of dominating sets 国際会議

    The 20th International Computing and Combinatorics Conference (COCOON 2014)　2014年8月4日

  25. Swapping labeled tokens on graphs 国際会議

    The 7th International Conference on FUN with Algorithms (FUN 2014)　2014年7月1日

  26. On the parameterized complexity for token jumping on graphs 国際会議

    The 11th Annual Conference on Theory and Applications of Models of Computation (TAMC 2014)　2014年4月11日

  27. On the parameterized complexity of reconfiguration problems 国際会議

    The 8th International Symposium on Parameterized and Exact Computation (IPEC 2013)　2013年9月4日

  28. On the minimum caterpillar problem in digraphs 国際会議

    The workshop in 19th Annual International Computing and Combinatorics Conference (COCOON 2013)　2013年6月21日

  29. Energy-efficient threshold circuits detecting global pattern in 1-dimensional arrays 国際会議

    The 10th Annual Conference on Theory and Applications of Models of Computation (TAMC 2013)　2013年5月20日

  30. Packing trominoes is NP-complete, #P-hard and ASP-complete 国際会議

    The 24th Canadian Conference on Computational Geometry (CCCG 2012)　2012年8月8日

  31. Hitori number 国際会議

    The 6th International Conference on Fun with Algorithms (FUN 2012)　2012年6月4日

  32. Energy-efficient threshold circuits detecting global pattern in 1-dimensional arrays 国際会議

    Tthe 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2013)　2012年4月19日

  33. Algorithm for the minimum caterpillar problem with terminals 国際会議

    The 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2013)　2012年4月19日

  34. Energy-efficient threshold circuits computing Mod functions 国際会議

    The Joint International Conference of 5th International Symposium and 4th Student Organizing International Mini-Conference on Information Electronics Systems　2012年2月23日

  35. On the rainbow connectivity of graphs: complexity and FPT algorithms 国際会議

    The 17th Annual International Computing and Combinatorics Conference (COCOON 2011)　2011年8月14日

  36. Energy and fan-in of threshold circuits computing Mod functions 国際会議

    The 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011)　2011年5月23日

  37. Energy-efficient threshold circuits computing Mod functions 国際会議

    The 17th Computing: the Australasian Theory Symposium (CATS 2011)　2011年1月17日

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

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

  1. 解空間グラフの編集に基づく遷移アルゴリズム基盤の構築

    鈴木 顕

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

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

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

    研究機関：Tohoku University

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

  2. 工学アプローチによる組合せ遷移の展開：配電切替を足がかりとして汎用ソルバーへ

    川原 純, 飯岡 大輔, 戸田 貴久, 宋 剛秀, 鈴木 顕, 照山 順一, 中畑 裕

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

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

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

    研究機関：Kyoto University

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

    詳細を見る 詳細を閉じる

    本研究では組合せ遷移の実装技術の構築とその産業応用に向けて、研究開発の共通基盤となるソフトウェア開発を目標とする。初年度にあたる本年度は、広く知られているグラフの独立集合の遷移問題（独立集合遷移問題）に対して、4種のアプローチを検討した。1つ目は、組合せ遷移の技法を用いたアルゴリズムの設計であり、主に、状態空間の部分探索の手法を検討した。2つ目は、SAT（充足可能性問題）ソルバーを活用するアプローチである。有限整数領域上の制約を命題論理式へと変換する SAT 符号化を行い、SATソルバーの強力な推論性能を用いて独立集合遷移問題を解くソルバーを開発した。3つ目は、ゼロサプレス型二分決定グラフ (ZDD) を活用するアプローチである。当初予定では、ZDD を上記2手法に援用した高速化を想定していたが、本研究において、ZDD が表す独立集合族を直接遷移させるアルゴリズムの開発に成功したため、ZDD を単独で用いて独立集合遷移問題を解くことが可能になった。4つ目の手法は、当初は予定していない新たな構想であるが、モデル検査と呼ばれる、システムの形式的な検査を可能にする技術を用いた手法である。入力グラフと開始、目標独立集合が与えられた際に、開始集合から目標集合に遷移可能ではないことを検証する記述をモデル検査ソルバーに与え、遷移可能な場合は反例として解となる遷移列を出力する。 以上の4つの技法について、アルゴリズム設計と実装を行った。アルゴリズムの比較実験のためには、適切な入力データが必要であるが、組合せ遷移問題に対する広く知られたベンチマークデータは存在しないため、入力データの作成整備を行った。 配電切替への組合せ遷移技術の適用についても研究を行い、配電切替を全域木遷移問題として定式化し、4つの技法の適用を検討して、実装を行っている。

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

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

    提供機関：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日

    詳細を見る 詳細を閉じる

    本研究は，研究領域「組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合」の総括班であり，その目的は「班間連携の促進」と「外部への広報活動」の大きく２つである．これらを実現するために，下記の通り活動を行った． まず，本年度の領域会議を2020年10月30日と2021年3月23日の２回完全オンラインにて開催した．１０月の領域会議では，本研究領域の全体像をメンバーらと再確認した．３月の領域会議では，班間連携を促進するためにも，各計画研究班の半年間の研究動向を報告し合い，研究討論を行った．また，１０月，３月の領域会議ともに，同日に一般公開のシンポジウムも併催した．１０月の公開シンポジウムは，キックオフミーティングと銘打って，本研究領域の目的と計画を中心に解説した．３月の公開シンポジウムでは，招待講演も企画した． さらにオンラインでは，組合せ遷移のセミナー・勉強会を継続して行った．2020年度中には７回開催し，それらは全て一般公開している．セミナー・勉強会は，本研究領域のメンバーが自身の研究を紹介することで，その背景分野を互いに勉強し合い，班間連携の促進につなげることを目的としている． この他にもアウトリーチ活動として，本研究領域Webサイトの開設，ニュースレター創刊号の発行，電気通信大学主催の産学官連携イベントでの発表などを行った． また，大容量メモリ搭載計算サーバを設置し，本研究領域のメンバーが利用できるように環境整備を行った．

  4. 組合せ遷移による常時稼働型システムの構成最適化

    鈴木 顕

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

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

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

    研究機関：Tohoku University

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

    詳細を見る 詳細を閉じる

    本年度は昨年度に引き続き本研究計画の2つの目標の内，1つ目の目標である「現実的な時間でより良い解を求めるアルゴリズムの開発」を中心に従事した．また，2つ目の「利便性の高いプログラムの実装と公開」にも従事した． 中でも大きな成果は，昨年より継続している彩色遷移問題の最適化遷移問題に関して，困難性容易性の両面から結果を得ることができた．具体的には，色数が少なくとも4で，入力グラフの縮退数が3の場合ですらNP困難，すなわち現実的な時間で解けそうにないほど難しい問題であることを示した．一方で，色数が3以下の場合や，入力グラフの縮退数が2以下の場合に動作する高速なアルゴリズムを開発した．これらの結果によって，色数と縮退数という2つの観点から本問題における困難性の境界を明らかにした．他にも，グラフクラスに基づく困難性の解析も行っており，平面グラフに対してNP困難である一方で，弦グラフやコグラフと呼ばれるグラフクラスに対しては線形時間アルゴリズムを与えた．これらの結果は既に「計算機と組合せ論に関する査読付き国際会議（COCOON 2021）」で口頭発表を行っており，またその際に提出した予稿は同国際会議より選抜論文として「情報数学と計算機科学に関する査読付き学術誌（IJCM:CST）」の特集号に招待され，現在査読中である． 他にも，全域木遷移問題に対して昨年から海外の研究者と行っていた，次数や直径を制限した際に問題の難しさがどう変わるかについての解析が終わり，この結果について「計算機科学の理論的側面に関する国際シンポジウム(STACS 2022)」で口頭発表を行った．

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

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

    提供機関：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日

    詳細を見る 詳細を閉じる

    本研究プロジェクトは，離散的な構造上における問題を中心に，その困難性に関する研究を行うプロジェクトであり，いくつかの方向性を持つ．まず解きたい問題を明確にし，定式化を行う．現実の問題をいかに抽象化・モデル化するかによって，問題の困難性は大きく異なって来る．次にその困難性の研究を行う．理論的に困難であれば，理論的な困難さの計算量的な根拠を示すことができる．一方，それが手に負えるとなれば，そこには具体的な解法，すなわちアルゴリズムが導かれる．こうして導かれた効率の良いアルゴリズムを実装し，実用的な速度で動作するかどうかを確認し，さらには元の現実の問題にフィードバックすることができる． 2020年度は新型コロナが急速に拡大し，当初計画していた対面での合宿形式の研究集会を十分に実施することができず，その中で研究方法も含めた模索が必要な年であった．行動が制限される中，研究者同士が柔軟に連絡を取りながら可能な範囲で共同研究を実施できた．理論的な困難性を示せた問題もあれば，効率の良いアルゴリズムを開発できた問題もある．また実際に実装して有効性を示せた問題もあった． 別紙に示す通り，2020年度は書籍3冊（研究書1冊と国際会議の会議録2冊）・査読付きのジャーナル論文18編・国際会議での発表27件を研究成果としてあげることができた． また2020年の後半には，本研究プロジェクトのメンバーを中心として，学術変革（A)（研究課題名：社会変革の源泉となる革新的アルゴリズム基盤の創出と体系化）および学術変革（B）（研究課題名：組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合）という大きな研究プロジェクトに採択され，本プロジェクトの研究の方向性をより大規模なものに発展させることができた．

  6. 遷移問題のパラメータ複雑性に関する研究

    鈴木 顕

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

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

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

    研究機関：Tohoku University

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

    詳細を見る 詳細を閉じる

    本研究では，パラメータ複雑度の観点から，遷移問題を解く高速なアルゴリズムの開発を行った．パラメータ複雑度とは，一般に解くことが難しいとされている問題のあるパラメータに着目し，問題の複雑性，すなわちそのパラメータが小さければ簡単に解くことができるのか，あるいは小さくてもなお難しい問題なのか，について研究する分野であり，問題の難しさの要因を明らかにするという理論的な興味だけでなく，実社会での応用時にも計算困難な問題を高速に解くための足掛かりとなる重要な研究である． 本研究では，様々な遷移問題に対して，容易性・困難性の両面から結果を与えることに成功した．

  7. エネルギーを制限したしきい値回路の計算限界の解明

    鈴木 顕

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

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

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

    研究機関：Tohoku University

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

    詳細を見る 詳細を閉じる

    本研究で得られた結果は大きく以下の2つである． 【結果１：一般化対称関数全てを計算することのできるエネルギー効率のよいしきい値回路の構成】本研究で与えた構成は，従来知られていたものに比べ，回路の規模が指数的に小さいものになっている． 【結果２：与えた構成の最適性の証明】この結果によって，エネルギーが小さい場合の結果１で与えた構成は，これ以上よくすることのできない最適な構成であることを示すことに成功した．

  8. 回路計算量理論に基づいた脳の計算原理の解明

    鈴木 顕

    2012年 ～ 2014年3月31日

    詳細を見る 詳細を閉じる

    昨年度の報告書で述べたとおり, 本年度は当初の予定を変更し, 「1. 計算時間を考慮したしきい値回路の設計および解析」に従事した. 昨年度従事した, 「2. より複雑な情報処理タスクの実現」に関する結果を利用することで, より厳密な計算時間の解析を行うことができた. 具体的には, 脳の情報処理の仕組みとして比較的研究の進んでいる画像認識に関わる関数を計算するしきい値回路に対して, 計算時間を制限した際にその計算能力にどのような影響があるかについて研究を行った. その結果, 計算時間を制限すると, 素子数やファンインが大きくならざるを得ないことを示すことに成功した. また, どの程度大きくする必要があるかについて解析を進めた結果, 最低限必要な素子数やファンインの値を正確に与えることに成功した. 研究結果の一部はすでに国際会議や学術雑誌に投稿済みであり, そのうちいくつかはすでに受理, 発表, 発行が済んでいる. 残る成果についても, 随時論文を執筆し, まとまり次第国際会議や学術雑誌に投稿する予定である. また, 本年度は昨年度得られた複数の結果についても, それぞれ国際会議「Asian Association forAlgorithms and Computation」及び「Theory and Applications of Models of Computation」等で発表を行った. さらに, 昨年度学術雑誌へ投稿していた論文は「Theoretical Computer Science (TCS)」受理され, 発行になった.

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