Details of the Researcher

PHOTO

Akira Suzuki
Section
Center for Data-driven Science and Artificial Intelligence
Job title
Professor
Degree

  • Ph.D. of Information Sciences (Tohoku University)

Research History 4

  • 2025/04 - Present
    Center for Data-driven Science and Artificial Intelligence, Tohoku University　Professor

  • 2019/05 - 2025/03
    Graduate School of Information Sciences, Tohoku University　Associate Professor

  • 2013/10 - 2019/04
    Graduate School of Information Sciences, Tohoku University　Assistant Professor

  • 2012/04 - 2013/09
    JSPS Research Fellow (DC1)

Education 4

  • Tohoku University　Graduate School of Information Sciences　Department of System Information Sciences

    2011/10 - 2013/09

  • Tohoku University　Graduate School of Information Sciences　Department of System Information Sciences

    2010/04 - 2011/09

  • Tohoku University　Faculty of Engineering　Department of Electrical,Information and Physics Engineering

    2006/04 - 2010/03

  • Makuhari Senior High School

    2003/04 - 2006/09

Committee Memberships 12

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

    2026/06 - Present

  • Division for Artificial Intelligence, Center for Data-driven Science and Artificial Intelligence, Tohoku University　Division Chief

    2026/04 - Present

  • Center for Data-driven Science and Artificial Intelligence, Tohoku University　Assistant Director

    2026/04 - Present

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

    2022 - Present

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

    2024/06 - 2026/06

  • LA Symposium　office

    2025/04 - 2026/03

  • 情報処理学会　代表会員

    2023/04 - 2025/03

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

    2020/05 - 2024/05

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

    2022/06 - 2023/06

  • LA Symposium　office

    2017/04 - 2018/03

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

    2023 -

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

    2022 -

Show all ︎Show first 5

Professional Memberships 2

  • The Institute of Electronics, Information and Communication Engineers

    2012/04 - Present

  • Information Processing Society of Japan

    2018/04 - 2025/03

Research Interests 3

  • Combinatorial Reconfiguration

  • Graph Algorithms

  • Computational complexity

Research Areas 1

  • Informatics / Information theory /

Awards 12

  1. Best Paper Award

    2025/02　The 19th International Conference and Workshops on Algorithms and Computation (WALCOM 2025)

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

    2024/03　東北大学

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

    2024/01　東北大学

  4. 2023年度 研究奨励賞

    2023/10　石田實記念財団

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

    2019/06　情報処理学会東北支部

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

    2015/04/18　船井情報科学振興財団

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

    2015/03/05　トーキン科学技術振興財団

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

    2015/02/04　井上科学振興財団

  9. President's Award

    2014/03/26　東北大学

  10. dean award

    2014/03/26　東北大学 大学院情報科学研究科

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

    2013/03/20　電子情報通信学会

  12. ECEI outstanding performance award

    2012/03/27　東北大学

Show all ︎Show 5

Papers 114

  1. Finding shortest reconfiguration sequence on independent set polytopes Peer-reviewed

    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/08

    DOI： 10.4230/LIPIcs.MFCS.2026.37 　

  2. On the complexity of k-colorable perfect matching Peer-reviewed

    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/07/15

    Publisher: 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 Peer-reviewed

    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/05

    DOI： 10.4230/LIPIcs.FUN.2026.25 　

  4. Spanning trees with a small vertex cover the complexity on specific graph classes Peer-reviewed

    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/02/13

    Publisher: Springer Nature Switzerland

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

    ISSN： 0302-9743

    eISSN： 1611-3349

  5. Reconfiguration of time-respecting arborescences Invited Peer-reviewed

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

    Algorithmica　88　(1-15)　1-16　2025/12/22

    Publisher: 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 Peer-reviewed

    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 Invited Peer-reviewed

    Tatsuhiro Suga, Akira Suzuki, Yuma Tamura, Xiao Zhou

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

    Publisher: 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 Peer-reviewed

    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

    Publisher: Elsevier BV

    DOI： 10.1016/j.tcs.2025.115425 　

    ISSN： 0304-3975

  11. Parameterized complexity of weighted target set selection Peer-reviewed

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

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

    Publisher: 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 Peer-reviewed

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

    Journal of Applied and Computational Topology　9　(3-21)　1-21　2025/09/04

    Publisher: 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 Peer-reviewed

    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/02/21

    Publisher: Springer Nature Singapore

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

    ISSN： 0302-9743

    eISSN： 1611-3349

  14. Multifaceted Evaluation of Distribution Network Configurations to Minimize Remaining Power Outage Peer-reviewed

    Shuhei Sugimura, Akihisa Kaneko, Yasuhiro Hayashi, Teppei Nozaki, Akira Suzuki, Takehiro Ito, Takayuki Tanabe

    IEEJ Transactions on Power and Energy　144　(12)　640-649　2024/12/01

    Publisher: Institute of Electrical Engineers of Japan (IEE Japan)

    DOI： 10.1541/ieejpes.144.640 　

    ISSN： 0385-4213

    eISSN： 1348-8147

  15. Scalable hard instances for independent set reconfiguration Peer-reviewed

    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/07

    Publisher: 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 Peer-reviewed

    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/07

    Publisher: ACM

    DOI： 10.1145/3659467.3659905 　

  17. Finding induced subgraphs from graphs with small mim-width Peer-reviewed

    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/06

    Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    DOI： 10.4230/LIPIcs.SWAT.2024.38 　

  18. Parameterized complexity of weighted target set selection Peer-reviewed

    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/05

    Publisher: Springer

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

  19. On the complexity of list H-packing for sparse graph classes Peer-reviewed

    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/03

    Publisher: Springer

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

  20. The shortest path reconfiguration problem based on relaxation of reconfiguration rules Peer-reviewed

    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/02/29

    Publisher: 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 Peer-reviewed

    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

    Publisher: 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 Peer-reviewed

    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/06

    Publisher: IEEE

    DOI： 10.1109/ictai59109.2023.00050 　

  24. Feedback vertex set reconfiguration in planar graphs Peer-reviewed

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

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

    Publisher: Elsevier BV

    DOI： 10.1016/j.tcs.2023.114188 　

    ISSN： 0304-3975

  25. Sorting balls and water: Equivalence and computational complexity Peer-reviewed

    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

    Publisher: Elsevier BV

    DOI： 10.1016/j.tcs.2023.114158 　

    ISSN： 0304-3975

  26. ZDD-Based Algorithmic Framework for Solving Shortest Reconfiguration Problems Peer-reviewed

    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/05/23

    Publisher: 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 Peer-reviewed

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

    Theoretical Computer Science　959　(113863)　1-17　2023/05

    Publisher: Elsevier BV

    DOI： 10.1016/j.tcs.2023.113863 　

    ISSN： 0304-3975

  28. Reconfiguration of Spanning Trees with Degree Constraints or Diameter Constraints Peer-reviewed

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

    Algorithmica　85　(9)　2779-2816　2023/04/10

    Publisher: 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 Peer-reviewed

    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/03/13

    Publisher: 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 Peer-reviewed

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

    Algorithmica　85　(11)　3348-3375　2023/03/06

    Publisher: 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 Peer-reviewed

    Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

    International Journal of Computer Mathematics: Computer Systems Theory　8　(1)　80-92　2023/01/02

    Publisher: 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 Peer-reviewed

    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

    Publisher: 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 Peer-reviewed

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

    Algorithmica　85　(11)　3327-3347　2022/12/15

    Publisher: 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 Peer-reviewed

    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

    Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    DOI： 10.4230/LIPIcs.ISAAC.2022.4 　

  37. Reconfiguring k-path vertex covers Peer-reviewed

    Duc A. HOANG, Akira SUZUKI, Tsuyoshi YAGITA

    IEICE Transactions on Information and Systems　E105.D　(7)　1258-1272　2022/07/01

    Publisher: 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 Peer-reviewed

    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/03/16

    Publisher: 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

    More details Close

    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. Peer-reviewed

    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

    Publisher: Springer

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

  43. Reconfiguration of Spanning Trees with Degree Constraint or Diameter Constraint Peer-reviewed

    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

    Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    DOI： 10.4230/LIPIcs.STACS.2022.15 　

  44. Sorting Balls and Water: Equivalence and Computational Complexity Peer-reviewed

    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

    Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    DOI： 10.4230/LIPIcs.FUN.2022.16 　

  45. Decremental Optimization of Vertex-Coloring Under the Reconfiguration Framework Peer-reviewed

    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

    Publisher: 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 Peer-reviewed

    Kei Kimura, Akira Suzuki

    Theoretical Computer Science　856　88-109　2021/02

    Publisher: Elsevier BV

    DOI： 10.1016/j.tcs.2020.12.025 　

    ISSN： 0304-3975

  47. Max-Min 3-Dispersion Problems. Peer-reviewed

    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 Peer-reviewed

    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

    Publisher: Elsevier BV

    DOI： 10.1016/j.tcs.2020.05.033 　

    ISSN： 0304-3975

  49. Parameterized complexity of independent set reconfiguration problems Peer-reviewed

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

    Discrete Applied Mathematics　283　336-345　2020/09

    Publisher: Elsevier BV

    DOI： 10.1016/j.dam.2020.01.022 　

    ISSN： 0166-218X

  50. Incremental optimization of independent sets under the reconfiguration framework Peer-reviewed

    Takehiro Ito, Haruka Mizuta, Naomi Nishimura, Akira Suzuki

    Journal of Combinatorial Optimization　43　(5)　1264-1279　2020/08/29

    Publisher: 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 Peer-reviewed

    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/05/29

    Publisher: 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 Peer-reviewed

    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/03/01

    Publisher: 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 Peer-reviewed

    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/02/20

    Publisher: 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 Peer-reviewed

    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/02/20

    Publisher: Springer International Publishing

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

    ISSN： 0302-9743

    eISSN： 1611-3349

  55. Reconfiguring spanning and induced subgraphs Peer-reviewed

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

    Theoretical Computer Science　806　553-566　2020/02

    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

    More details Close

    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

    More details Close

    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 Peer-reviewed

    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

    Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    DOI： 10.4230/LIPIcs.ESA.2020.24 　

  59. Fixed-Parameter Algorithms for Graph Constraint Logic Peer-reviewed

    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

    Publisher: 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

    More details Close

    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 Peer-reviewed

    Takehiro Ito, Haruka Mizuta, Naomi Nishimura, Akira Suzuki

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

    Publisher: Springer

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

  64. Sequentially Swapping Colored Tokens on Graphs. Peer-reviewed

    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. Peer-reviewed

    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

    Publisher: Springer

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

  66. Max-Min 3-Dispersion Problems. Peer-reviewed

    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

    Publisher: Springer

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

  67. Computational Power of Threshold Circuits of Energy at most Two Peer-reviewed

    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/09/01

    Publisher: Institute of Electronics, Information and Communications Engineers (IEICE)

    DOI： 10.1587/transfun.e101.a.1431 　

    ISSN： 0916-8508

    eISSN： 1745-1337

  68. グラフの色付きトークン整列問題について

    Konno, Hayato, Suzuki, Akira, Yamanaka, Katsuhisa, Ito, Takehiro, Zhou, Xiao

    RIMS Kokyuroku　2088　53-62　2018/08

    Publisher:

    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

    More details Close

    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. Peer-reviewed

    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

    Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik

    DOI： 10.4230/LIPIcs.ISAAC.2018.37 　

  72. Reconfiguring spanning and induced subgraphs Peer-reviewed

    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

    Publisher: Springer

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

  73. The complexity of (List) edge-coloring reconfiguration problem Peer-reviewed

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences　E101A　(1)　232-238　2018/01/01

    Publisher: 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 Peer-reviewed

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    Leibniz International Proceedings in Informatics, LIPIcs　92　62:1-62:12　2017/12/01

    Publisher: 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 Peer-reviewed

    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" Peer-reviewed

    Masanori Fukui, Koki Suetsugu, Akira Suzuki

    The 20th Anniversary of Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2017)　2017/09/01

  77. Hitori numbers Peer-reviewed

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

    Journal of Information Processing　25　695-707　2017/08/01

    Publisher: Information Processing Society of Japan

    DOI： 10.2197/ipsjjip.25.695 　

    ISSN： 1882-6652 0387-5806

  78. On the Parameterized Complexity of Reconfiguration Problems Peer-reviewed

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

    ALGORITHMICA　78　(1)　274-297　2017/05

    DOI： 10.1007/s00453-016-0159-2 　

    ISSN： 0178-4617

    eISSN： 1432-0541

  79. The Complexity of (List) Edge-Coloring Reconfiguration Problem Peer-reviewed

    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 Peer-reviewed

    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 Invited Peer-reviewed

    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 Peer-reviewed

    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 Peer-reviewed

    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/06/24

    Publisher: 電子情報通信学会

    ISSN： 0913-5685

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

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

    第158回アルゴリズム研究会　1-7　2016/06

  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 Invited Peer-reviewed

    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/06

    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 Invited Peer-reviewed

    Takashi Hasegawa, Takehiro Ito, Akira Suzuki, Xiao Zhou

    Interdisciplinary Information Sciences (IIS)　21　(1)　25-36　2015/03/20

    Publisher: Tohoku University

    DOI： 10.4036/iis.2015.25 　

    ISSN： 1340-9050

    More details Close

    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 Peer-reviewed

    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

    Publisher: Springer Verlag

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

    ISSN： 1611-3349 0302-9743

  91. Competitive diffusion on weighted graphs Peer-reviewed

    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

    Publisher: Springer Verlag

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

    ISSN： 1611-3349 0302-9743

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

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

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

  93. On the Minimum Caterpillar Problem in Digraphs Peer-reviewed

    Taku Okada, Akira Suzuki, Takehiro Ito, Xiao Zhou

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

    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

    More details Close

    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 Peer-reviewed

    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 Peer-reviewed

    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 Peer-reviewed

    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 Invited Peer-reviewed

    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 Invited Peer-reviewed

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    THEORETICAL COMPUTER SCIENCE　505　74-80　2013/09

    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 Peer-reviewed

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    Proceedings of the 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2013)　17-17　2013/04/20

  102. Algorithm for the minimum caterpillar problem with terminals Peer-reviewed

    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/04/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 Invited Peer-reviewed

    Akira Suzuki, Kei Uchizawa, Xiao Zhou

    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE　24　(1)　15-29　2013/01

    DOI： 10.1142/S0129054113400029 　

    ISSN： 0129-0541

  105. Energy-efficient threshold circuits detecting global pattern in 1-dimentional arrays Peer-reviewed

    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

    Publisher: Springer Verlag

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

    ISSN： 1611-3349 0302-9743

  106. On the minimum caterpillar problem in digraphs Peer-reviewed

    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

    Publisher: Springer

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

    ISSN： 0302-9743 1611-3349

  107. On the parameterized complexity of reconfiguration problems Peer-reviewed

    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

    Publisher: Springer

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

    ISSN： 0302-9743 1611-3349

  108. On the Complexity of Packing Trominoes

    HORIYAMA Takashi, ITO Takehiro, NAKATSUKA Keita, SUZUKI Akira, UEHARA Ryuhei

    IEICE technical report. Theoretical foundations of Computing　112　(272)　37-43　2012/10/24

    Publisher: 一般社団法人電子情報通信学会

    ISSN： 0913-5685

    More details Close

    We study the computational complexity of packing puzzles of identical polyominoes. Packing dominoes (i.e., 1×2 rectangles) into grid polygons can be solved in polynomial time by reducing to a bipartite matching problem. On the other hand, packing 2×2 squares is known to be NP-complete. In this paper, we fill the gap between dominoes and 2×2 squares, that is, we consider the packing puzzles of trominoes. Note that there exist only two shapes of trominoes: L-shape and I-shape. We show that their packing problems are both NP-complete. Our reductions are carefully designed so that we can also prove #P-completeness and ASP-completeness of the counting and the another-solution-problem variants, respectively. (This article is a technical report without peer review.)

  109. Packing trominoes is NP-complete, #P-hard and ASP-complete Peer-reviewed

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

    Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012)　219-224　2012/08/09

  110. Packing Trominoes is NP-Complete, #P-Complete and ASP-Complete. Peer-reviewed

    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 Peer-reviewed

    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

    Publisher: Springer

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

    ISSN： 0302-9743 1611-3349

  112. Energy-efficient threshold circuits computing Mod functions Peer-reviewed

    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/01/20

    Publisher: Australian Computer Society

  113. Energy and Fan-In of Threshold Circuits Computing Mod Functions Peer-reviewed

    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 Peer-reviewed

    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

    Publisher: Springer

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

    ISSN： 0302-9743 1611-3349

Show all ︎Show first 5

Misc. 31

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

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

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

  2. Independent Set and Vertex Cover Reconfiguration Under Extended Rules

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

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

  3. Shortest Path Reconfiguration with Relaxed Constraints

    DOMON Naoki, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

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

  4. Algorithms for Weighted Target Set Selection

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

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

    ISSN： 1349-144X

  5. The Independent Set Reconfiguration Problem Based on Relaxation of Reconfiguration Rules

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

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

    ISSN： 1349-144X

  6. On software for combinatorial reconfiguration problems

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

    情報処理学会研究報告(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/09

    Publisher: 東京 : 電気学会

  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/09

    Publisher: 東京 : 電気学会

  9. On the Problems of Finding Paths to Avoid Ordered Forbidden Transitions Based on Graph Structure

    KUMAKURA Kota, SUZUKI Akira, TAMURA Yuma, ZHOU Xiao

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

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

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

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

    ISSN： 1883-1893

  11. The Hamiltonian Cycle Reconfiguration Problem for Interval Graphs

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

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

    ISSN： 1349-144X

  12. Optimization Variant of Vertex-Coloring Reconfiguration Problem

    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/09

    Publisher: 東京 : 電気学会

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

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

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

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

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

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

  16. Method for Distribution Loss Minimization and Switching Operation Procedures with Radial Network Reconfiguration

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

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

  17. Linear-Time Algorithms for the Generalized Coloring Reconfiguration Problem

    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

    Publisher: 電子情報通信学会

    ISSN： 0913-5685

  19. Hitori Numbers

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

    58　(8)　2017/08/15

    ISSN： 1882-7764

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

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

    数理解析研究所講究録　(2040)　21-26　2017/07

    Publisher: 京都大学数理解析研究所

    ISSN： 1880-2818

  21. Algorithm for Generalized Coloring Reconfiguration Problem

    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. Theoretical foundations of Computing　114　(80)　9-12　2014/06/13

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    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

    IPSJ SIG Notes　2014　(2)　1-4　2014/06/06

    Publisher: Information Processing Society of Japan (IPSJ)

    ISSN： 0919-6072

    More details Close

    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. The Server Supply-Assignment Problem on Graphs under a Given Routing Table (New Streams of Computation Theory and Algorithms)

    Oohino Hajime, Ito Takehiro, Suzuki Akira, Uchizawa Kei, Zhou Xiao

    RIMS Kokyuroku　1894　41-44　2014/05

    Publisher: Kyoto University

    ISSN： 1880-2818

  25. Reconfiguration of Dominating Sets (Theoretical Foundations of Computing)

    SUZUKI Akira, Mouawad Amer E., Nishimura Naomi

    IEICE technical report. Theoretical foundations of Computing　114　(19)　29-35　2014/04/24

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    We explore a reconfiguration version of the dominating set problem, where a dominating set in a graph G is a set S of vertices such that each vertex is either in S or has a neighbour in S. In a reconfiguration problem, the goal is to determine whether there exists a sequence of feasible solutions connecting given feasible solutions s and t such that each pair of consecutive solutions is adjacent according to a specified adjacency relation. Two dominating sets are adjacent if one can be formed from the other by the addition or deletion of a single vertex. For various values of k, we consider properties of D_k(G), the graph consisting of a vertex for each dominating set of size at most k and edges specified by the adjacency relation. Addressing an open question posed by Haas and Seyffarth, we demonstrate that D_<Γ(G)+1>(G) is not necessarily connected, for Γ(G) the maximum cardinality of a minimal dominating set in G. The result holds even when graphs are constrained to be planar, of bounded tree-width, or b-partite for b≧3. Moreover, we construct an infinite family of graphs such that D_<γ(G)+1>(G) has exponential diameter, for _γ(G) the minimum size of a dominating set. On the positive side, we show that D_<n-m>(G) is connected and of linear diameter for any graph G on n vertices having at least m+1 independent edges.

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

    Suzuki Akira, Uchizawa Kei, Zhou Xiao

    RIMS Kokyuroku　1849　133-134　2013/08

    Publisher: Kyoto University

  27. DS-1-5 Hitori Number

    Suzuki Akira, Uchizawa Kei, Uno Takeaki

    Proceedings of the IEICE General Conference　2012　(1)　"S-9"-"S-10"　2012/03/06

    Publisher: The Institute of Electronics, Information and Communication Engineers

    More details Close

    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 Energy and Fan-in of Threshold Circuits Computing Mod Functions

    Suzuki Akira, Uchizawa Kei, Xiao Zhou

    Proceedings of the IEICE General Conference　2011　(1)　"S-7"-"S-8"　2011/02/28

    Publisher: The Institute of Electronics, Information and Communication Engineers

    More details Close

    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

    2011　(4)　1-8　2011/02/28

    Publisher: 情報処理学会

    ISSN： 2186-2583

  30. Hardness and FPT Algorithm for the Rainbow Connectivity of Graphs

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

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

    ISSN： 2186-2583

  31. Energy-Efficient Threshold Circuits Computing Mod Functions

    SUZUKI Akira, UCHIZAWA Kei, ZHOU Xiao

    IEICE technical report　110　(325)　7-13　2010/11/26

    Publisher: The Institute of Electronics, Information and Communication Engineers

    ISSN： 0913-5685

    More details Close

    We prove that the modulus function MOD_m of n variables can be computed by a threshold circuit C of energy e and size s=O(e(n/m)^<1/(e-1)>) for any integer e≧2, where the energy e is defined to be the maximum number of gates outputting "1" over all inputs to C, and the size s to be the number of gates in C. Our upper bound on the size s almost matches the known lower bound s=Ω(e(n/m)^<1/e)).

Show all ︎Show first 5

Books and Other Publications 1

  1. Algorithms for Machine Learning

    2021/06

Presentations 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/09/07

  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/06/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/04/02

  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/04/01

  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/03/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/07/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/07/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/07/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/05/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/07/03

  14. Complexity of Coloring Reconfiguration under Recolorability Constraints International-presentation

    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 International-presentation

    Akira Suzuki

    2017 Bilateral Workshop between Tohoku University and National Tsing Hua University　2017/10/13

  16. Complexity of "Goishi Hiroi" International-presentation

    Masanori Fukui, Koki Suetsugu, Akira Suzuki

    The 20th Anniversary of Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2017)　2017/08/29

  17. The complexity of (list) edge-coloring reconfiguration problem International-presentation

    Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

    The 11th International Conference and Workshops on Algorithms and Computation (WALCOM 2017)　2017/03/29

  18. Sequentially swapping colored tokens on graphs International-presentation

    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/03/29

  19. Reduction tools on NCL International-presentation

    Akira Suzuki

    The Second International Workshop on Combinatorial Reconfiguration (CoRe 2017), Combinatorial Reconfiguration (17w5066)　2017/01/22

  20. The multi-service center decision problem is NP-complete for split graphs International-presentation

    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 International-presentation

    The 14th Algorithms and Data Structures Symposium (WADS 2015)　2015/08/05

  22. Competitive diffusion on weighted graphs International-presentation

    The 14th Algorithms and Data Structures Symposium (WADS 2015)　2015/08/05

  23. Algorithms for maintaining shortest-paths trees on real-world networks International-presentation

    Data Science in Life Science and Engineering Collaboration and Symposium　2015/07/29

  24. Reconfiguration of dominating sets International-presentation

    The 20th International Computing and Combinatorics Conference (COCOON 2014)　2014/08/04

  25. Swapping labeled tokens on graphs International-presentation

    The 7th International Conference on FUN with Algorithms (FUN 2014)　2014/07/01

  26. On the parameterized complexity for token jumping on graphs International-presentation

    The 11th Annual Conference on Theory and Applications of Models of Computation (TAMC 2014)　2014/04/11

  27. On the parameterized complexity of reconfiguration problems International-presentation

    The 8th International Symposium on Parameterized and Exact Computation (IPEC 2013)　2013/09/04

  28. On the minimum caterpillar problem in digraphs International-presentation

    The workshop in 19th Annual International Computing and Combinatorics Conference (COCOON 2013)　2013/06/21

  29. Energy-efficient threshold circuits detecting global pattern in 1-dimensional arrays International-presentation

    The 10th Annual Conference on Theory and Applications of Models of Computation (TAMC 2013)　2013/05/20

  30. Packing trominoes is NP-complete, #P-hard and ASP-complete International-presentation

    The 24th Canadian Conference on Computational Geometry (CCCG 2012)　2012/08/08

  31. Hitori number International-presentation

    The 6th International Conference on Fun with Algorithms (FUN 2012)　2012/06/04

  32. Energy-efficient threshold circuits detecting global pattern in 1-dimensional arrays International-presentation

    Tthe 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2013)　2012/04/19

  33. Algorithm for the minimum caterpillar problem with terminals International-presentation

    The 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2013)　2012/04/19

  34. Energy-efficient threshold circuits computing Mod functions International-presentation

    The Joint International Conference of 5th International Symposium and 4th Student Organizing International Mini-Conference on Information Electronics Systems　2012/02/23

  35. On the rainbow connectivity of graphs: complexity and FPT algorithms International-presentation

    The 17th Annual International Computing and Combinatorics Conference (COCOON 2011)　2011/08/14

  36. Energy and fan-in of threshold circuits computing Mod functions International-presentation

    The 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011)　2011/05/23

  37. Energy-efficient threshold circuits computing Mod functions International-presentation

    The 17th Computing: the Australasian Theory Symposium (CATS 2011)　2011/01/17

Show all Show first 5

Research Projects 8

  1. Development of a Reconfiguration Algorithm Framework Based on Solution Space Modifications

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    2025/04/01 - 2028/03/31

  2. Engineering Approach for Expanding Combinatorial Reconfiguration: Toward a General-Purpose Solver Using Power Distribution Systems as a Steppingstone

    KAWAHARA Jun

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Transformative Research Areas (B)

    Institution: Kyoto University

    2020/10/02 - 2023/03/31

    More details Close

    In this study, we developed an implementation technology for combinatorial reconfiguration problems and studied it for industrial applications. Specifically, we proposed algorithms based on bounded model checking and binary decision diagrams. We also developed four kinds of software and libraries containing them, and made them publicly available for easy use by non-specialists. For industrial applications, we worked on the computation of a multi-stage switching procedure of power distribution networks, and developed a program using our solver. It is theoretically guaranteed that the obtained procedure is the shortest. During the 3.5 years of research including the carry-over period, we published 48 peer-reviewed academic papers.

  3. Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration

    ITO Takehiro

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Transformative Research Areas (B)

    Institution: Tohoku University

    2020/10/02 - 2023/03/31

    More details Close

    To facilitate smooth collaboration among researchers with backgrounds in computer science, engineering, and mathematics, and to widely publicize their research outcomes, we effectively managed this research project. To promote inter-group collaboration, we organized six project meetings, 35 seminars, and published five issues of newsletters. All of these activities were made publicly available. Additionally, we hosted numerous events across various fields. These included three co-located workshops at the international conference ICALP, four online one-day international workshops, two international programming competitions on combinatorial reconfiguration, two student symposia on combinatorial reconfiguration, and four outreach events.

  4. Optimization of always-on systems by combinatorial reconfigurations

    SUZUKI Akira

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (C)

    Institution: Tohoku University

    2020/04/01 - 2023/03/31

    More details Close

    The theoretical results were obtained from the optimized reconfiguration problem for the independent set and the coloring problem, and results were obtained in terms of both intractability and tractability. Specifically, we conducted complexity analysis using parameters such as the degeneracy and solution size, and we analyzed the intractability based on graph classes. In the latter case, we clarified the boundary of the complexity from the viewpoints of the number of colors and degeneracy. These studies have been recognized as academic achievements, as evidenced by their acceptance in peer-reviewed journals. On the application side, we have implemented and released a combinatorial reconfiguration solver in collaboration with other researchers and research projects. Additionally, we presented the algorithms operating within the implemented and released programs in oral presentations.

  5. Research on algorithms and data structures for solving theoretically hard problems in practical time

    Uehara Ryuhei

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Scientific Research (A)

    Institution: Japan Advanced Institute of Science and Technology

    2018/04/01 - 2023/03/31

    More details Close

    In recent decades, computational power has improved remarkably. However, contrary to what most users would imagine, the main factor behind the improvement in the speed at which computers solve problems is not the improvement in hardware performance, but the development of the software on top of it, especially algorithms and data structures, which has made a significant contribution. In this research theme, we first demonstrated the theoretical difficulty of various combinatorial optimization problems, and then used the problem properties revealed in the process to design and develop algorithms for solving the problems efficiently.

  6. On the parameterized complexity of the reconfiguration problems

    Suzuki Akira

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Young Scientists (B)

    Institution: Tohoku University

    2017/04/01 - 2020/03/31

    More details Close

    In this research, we treat a fast algorithm for solving the reconfiguration problems from the viewpoint of parameterized complexity. Parameterized complexity is a field to study the complexity of a problem, focusing on the parameters of the problem that are generally difficult to solve. In other words, we investigate that when the parameter of a problem is small, can the problem be solved easily, or still difficult. This research is not only a theoretical interest in clarifying the factor of the difficulty of the problem, but also an important research that serves as a stepping-stone for solving a difficult-to-calculate problem at the time of application in the real world. In this research, we succeeded in giving results to various reconfiguration problems in terms of both ease and difficulty.

  7. Elucidation of comptational limit of threshold circuit with restricted energy

    SUZUKI Akira

    Offer Organization: Japan Society for the Promotion of Science

    System: Grants-in-Aid for Scientific Research

    Category: Grant-in-Aid for Young Scientists (B)

    Institution: Tohoku University

    2014/04/01 - 2017/03/31

    More details Close

    The main results of this research are the following two: Result 1. We give the constructions of energy-efficient threshold circuits computing generalized symmetric functions. In addition, our constructions improve the size of threshold circuit exponentially, compared with known ones. Result 2. We show the optimality of our constructions. By this result, we show that the construction we give in Result 1 is optimal, that is, no one can construct with smaller number of gates than our construction.

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

    鈴木 顕

    Offer Organization: 日本学術振興会

    System: 科学研究費助成事業

    Category: 特別研究員奨励費

    Institution: 東北大学

    2012 - 2014/03/31

    More details Close

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

Show all Show first 5