活動情報

論文・受賞

A01

  • Reconfiguration of colorings in triangulations of the sphere

    Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
    Proc. of 39th International Symposium on Computational Geometry (SoCG 2023), Leibniz International Proceedings in Informatics, Vol. 258, pp. 43:1-43:16, 2023
    • 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, Vol. 978, Article 114158, 2023
      • Algorithmic theory of qubit routing

        Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
        Proc. of 18th Algorithms and Data Structures Symposium (WADS 2023), Lecture Notes in Computer Science, Vol. 14079, pp. 533–546, 2023
        • On reachable assignments under dichotomous preferences

          Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
          Theoretical Computer Science, Vol. 979, Article 114196, 2023
          • 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, Vol. 85, pp. 2779–2816, 2023
            • Fixed-parameter algorithms for graph constraint logic

              Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, Akira Suzuki
              Theoretical Computer Science, Vol. 959, Article 113863, 2023
              • Reconfiguration and enumeration of optimal cyclic ladder lotteries

                Yuta Nozaki, Katsuhisa Yamanaka, Kunihiro Wasa
                Proc. of 34th International Workshop on Combinatorial Algorithms (IWOCA 2023), Lecture Notes in Computer Science, Vol. 13889, pp. 331-342, 2023
                • Rerouting planar curves and disjoint paths

                  Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
                  Proc. of 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023), Leibniz International Proceedings in Informatics, Vol. 261, pp. 81:1-81:19, 2023
                  • Polynomial-delay enumeration of large maximal common independent sets in two matroids

                    Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
                    Proc. of 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023), Leibniz International Proceedings in Informatics, Vol. 272, pp. 58:1-58:14, 2023
                    • Reconfiguration of time-respecting arborescences

                      Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira Suzuki
                      Proc. of 18th Algorithms and Data Structures Symposium (WADS 2023), Lecture Notes in Computer Science, Vol. 14079, pp. 521-532, 2023
                      • Reconfiguration of vertex-disjoint shortest paths on graphs

                        Rin Saito, Hiroshi Eto, Takehiro Ito, Ryuhei Uehara
                        Proc. of 17th International Conference and Workshops on Algorithms and Computation (WALCOM 2023), Lecture Notes in Computer Science, Vol. 13973, pp. 191-201, 2023
                        • Approximability of the distance independent set problem on regular graphs and planar graphs

                          Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano
                          IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E105-A, pp. 1211-1222, 2022
                          • Reconfiguration of cliques in a graph

                            Takehiro Ito, Hirotaka Ono, Yota Otachi
                            Discrete Applied Mathematics, Vol. 333, pp. 43-58, 2023
                            • Sequentially swapping tokens: Further on graph classes

                              Hironori Kiya, Yuto Okada, Hirotaka Ono, Yota Otachi
                              Proc. of 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2023), Lecture Notes in Computer Science, Vol. 13878, pp. 222-235, 2023
                              • Extended MSO model checking via small vertex integrity

                                Tatsuya Gima, Yota Otachi
                                Proc. of 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz International Proceedings in Informatics, Vol. 248, pp. 20:1-20:15, 2022
                                • On reachable assignments under dichotomous preferences

                                  Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
                                  Proc. of 24th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA 2022), Lecture Notes in Computer Science, Vol. 13753, pp. 650-658, 2022
                                  • Happy set problem on subclasses of co-comparability graphs

                                    Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura
                                    Algorithmica, Vol. 85, Article 44947, 2023
                                    • ZDD-based algorithmic framework for solving shortest reconfiguration problems

                                      Takehiro Ito, Jun Kawahara, Yu Nakahata, Takehide Soh, Akira Suzuki, Junichi Teruyama, Takahisa Toda
                                      Proc. of 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2023), Lecture Notes in Computer Science, Vol. 13884, pp. 167-183, 2023
                                      • Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

                                        Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
                                        ACM Transactions on Algorithms, Vol. 19, Article 6, 2023
                                        • A framework to design approximation algorithms for finding diverse solutions in combinatorial problems

                                          Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi
                                          Proc. of 37th AAAI Conference on Artificial Intelligence (AAAI 2023), AAAI-23 Technical Tracks 4, Vol. 37, pp. 3968-3976, 2023
                                          • Reconfiguring (non-spanning) arborescences

                                            Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa
                                            Theoretical Computer Science, Vol. 943, pp. 131-141, 2023
                                            • 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
                                              Proc. of 11th International Conference on Fun with Algorithms (FUN 2022), Leibniz International Proceedings in Informatics, Vol. 226, pp. 16:1-16:17, 2022
                                              • A parameterized view to the robust recoverable base problem of matroids under structural uncertainty

                                                Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
                                                Operations Research Letters, Vol. 50, pp. 370-375, 2022
                                                • An improved deterministic parameterized algorithm for cactus vertex deletion

                                                  Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi
                                                  Theory of Computing Systems, Vol. 66, pp. 502-515, 2022
                                                  • Parameterized complexity of non-separating and non-disconnecting paths and sets

                                                    Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi, Saket Saurabh
                                                    Proc. of 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Leibniz International Proceedings in Informatics, Vol. 241, pp. 6:1-6:15, 2022
                                                    • Algorithmic meta-theorems for combinatorial reconfiguration revisited

                                                      Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi
                                                      Proc. of 30th Annual European Symposium on Algorithms (ESA 2022), Leibniz International Proceedings in Informatics, Vol. 244, pp. 61:1-61:15, 2022
                                                      • Polynomial-delay and polynomial-space enumeration of large maximal matchings

                                                        Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
                                                        Proc. of 48th edition of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG2022), Vol. 13453, pp. 342-355, 2022
                                                        • Linear-delay enumeration for minimal Steiner problems

                                                          Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
                                                          Proc. of 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2022), pp. 301-313, 2022
                                                          • Constant amortized time enumeration of Eulerian trails

                                                            Kazuhiro Kurita, Kuniihiro Wasa
                                                            Theoretical Computer Science, Vol. 923, Article 44573, 2022
                                                            • Independent set reconfiguration on directed graphs

                                                              Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, Kunihiro Wasa
                                                              Proc. of 47th International Symposium on Mathematical Foundations of Computer Science, Leibniz International Proceedings in Informatics, Vol. 241, pp. 58:1-58:15, 2022
                                                              • Shortest reconfiguration of perfect matchings via alternating cycles

                                                                Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
                                                                SIAM Journal on Discrete Mathematics, Vol. 36, pp. 1102-1123, 2022
                                                                • Parameterized complexity of graph burning

                                                                  Yasuaki Kobayashi, Yota Otachi
                                                                  Algorithmica, Vol. 84, pp. 2379-2393, 2022
                                                                  • Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

                                                                    Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
                                                                    Proc. of Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pp. 1342-1355, 2022
                                                                    • Linear-time recognition of double-threshold graphs

                                                                      Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno
                                                                      Algorithmica, Vol. 84, pp. 1163-1181, 2022
                                                                      • Reforming an envy-free matching

                                                                        Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
                                                                        Proc. of 36th AAAI Conference on Artificial Intelligence (AAAI 2022), Vol. 36, pp. 5084-5091, 2022
                                                                        • Computing diverse shortest paths efficiently: A theoretical and experimental study

                                                                          Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, Yota Otachi
                                                                          Proc. of 36th AAAI Conference on Artificial Intelligence (AAAI 2022), Vol. 36, pp. 3758-3766, 2022
                                                                          • Finding diverse trees, paths, and more

                                                                            Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi
                                                                            Proc. of the AAAI Conference on Artificial Intelligence (AAAI 2021), Vol. 35, pp. 3778-3786, 2021
                                                                            • 情報処理学会 2022年度山下記念研究賞

                                                                              和佐 州洋 (法政大学)
                                                                              「Constant Amortized Time Enumeration of Eulerian trails (2021-AL-183)」
                                                                              2023年3月2日受賞
                                                                              • Parameterized complexity of (A, l)-path packing

                                                                                Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi
                                                                                Algorithmica, Vol. 84, pp. 871-895, 2022
                                                                                • Reconfiguration of regular induced subgraphs

                                                                                  Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, Kunihiro Wasa
                                                                                  Proc. of 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), Lecture Notes in Computer Science, Vol. 13174, pp. 35-46, 2022
                                                                                  • Happy set problem on subclasses of co-comparability graphs

                                                                                    Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura
                                                                                    Proc. of 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), Lecture Notes in Computer Science, Vol. 13174, pp. 149-160, 2022
                                                                                    • Reconfiguration of spanning trees with degree constraint or diameter constraint

                                                                                      Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, Kunihiro Wasa
                                                                                      Proc. of 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Leibniz International Proceedings in Informatics, Vol. 219, pp. 15:1-15:21, 2022
                                                                                      • An O(n^2)-time algorithm for computing a max-min 3-dispersion on a point set in convex position

                                                                                        Yasuaki Kobayashi, Shin-Ichi Nakano, Kei Uchizawa, Takeaki Uno, Yutaro Yamaguchi, Katsuhisa Yamanaka
                                                                                        IEICE Transactions on Information and Systems, Vol. E105-D, pp. 503-507, 2022
                                                                                        • On the security number of the Cartesian product of graphs

                                                                                          Marko Jakovac, Yota Otachi
                                                                                          Discrete Applied Mathematics, Vol. 304, pp. 119-128, 2021
                                                                                          • Distributed reconfiguration of spanning trees

                                                                                            Yukiko Yamauchi, Naoyuki Kamiyama, Yota Otachi
                                                                                            Proc. of 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2021), Lecture Notes in Computer Science, Vol. 13046, pp. 516-520, 2021
                                                                                            • Efficient enumeration of dominating sets for sparse graphs

                                                                                              Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
                                                                                              Discrete Applied Mathematics, Vol. 303, pp. 283-295, 2021
                                                                                              • Low-congestion shortcut and graph parameters

                                                                                                Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi
                                                                                                Distributed Computing, Vol. 34, pp. 349-365, 2021
                                                                                                • Computational complexity of jumping block puzzles

                                                                                                  Masaaki Kanzaki, Yota Otachi, Ryuhei Uehara
                                                                                                  Proc. of 27th International Computing and Combinatorics Conference (COCOON 2021), Lecture Notes in Computer Science, Vol. 13025, pp. 655-667, 2021
                                                                                                  • Reconfiguring directed trees in a digraph

                                                                                                    Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa
                                                                                                    Proc. of 27th International Computing and Combinatorics Conference (COCOON 2021), Lecture Notes in Computer Science, Vol. 13025, pp. 343-354, 2021
                                                                                                    • 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, Vol. E104-A, pp. 1101-1107, 2021
                                                                                                      • Longest common subsequence in sublinear space

                                                                                                        Masashi Kiyomi, Takashi Horiyama, Yota Otachi
                                                                                                        Information Processing Letters, Vol. 168, pp. 106084, 2021
                                                                                                        • A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number

                                                                                                          Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura
                                                                                                          Theoretical Computer Science, Vol. 874, pp. 32-41, 2021
                                                                                                          • A (probably) optimal algorithm for bisection on bounded-treewidth graphs

                                                                                                            Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone
                                                                                                            Theoretical Computer Science, Vol. 873, pp. 38-46, 2021
                                                                                                            • Finding diverse trees, paths, and more

                                                                                                              Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi
                                                                                                              Proc. of the AAAI Conference on Artificial Intelligence (AAAI 2021), Vol. 35, pp. 3778-3786, 2021
                                                                                                              DOI: 
                                                                                                              • Algorithms for gerrymandering over graphs

                                                                                                                Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
                                                                                                                Theoretical Computer Science, Vol. 868, pp. 30-45, 2021
                                                                                                                • Exploring the gap between treedepth and vertex cover through vertex integrity

                                                                                                                  Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi
                                                                                                                  Proc. of 12th International Conference on Algorithms and Complexity (CIAC 2021), Lecture Notes in Computer Science, Vol. 12701, pp. 271-285, 2021
                                                                                                                  • Finding a maximum minimal separator: Graph classes and fixed-parameter tractability

                                                                                                                    Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Tsuyoshi Yagita
                                                                                                                    Theoretical Computer Science, Vol. 865, pp. 131-140, 2021
                                                                                                                    • Optimal reconfiguration of optimal ladder lotteries

                                                                                                                      Katsuhisa Yamanaka, Takashi Horiyama, Kunihiro Wasa
                                                                                                                      Theoretical Computer Science, Vol. 859, pp. 57-69, 2021
                                                                                                                      • Computing the largest bond and the maximum connected cut of a graph

                                                                                                                        Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Daniel Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, Uéverton S. Souza
                                                                                                                        Algorithmica, Vol. 83, pp. 1421-1458, 2021
                                                                                                                        • Approximability of the independent feedback vertex set problem for bipartite graphs

                                                                                                                          Yuma Tamura, Takehiro Ito, Xiao Zhou
                                                                                                                          Theoretical Computer Science, Vol. 849, pp. 227-236, 2021
                                                                                                                          • FIT2020 船井ベストペーパー賞

                                                                                                                            岡本 吉央 (電気通信大学),伊藤 健洋 (東北大学),垣村 尚徳 (慶應義塾大学),神山 直之 (九州大学),小林 佑輔 (京都大学)
                                                                                                                            「構造変化に応じるロバスト修復可能マトロイド基問題に対する固定パラメータアルゴリズム」
                                                                                                                            2021年8月26日受賞
                                                                                                                            • 2020年度 人工知能学会 研究会優秀賞

                                                                                                                              土中 哲秀 (中央大学),小林 靖明 (京都大学),栗田 和宏 (国立情報学研究所),大舘 陽太 (名古屋大学)
                                                                                                                              「多様な部分グラフを発見するアルゴリズム」
                                                                                                                               2021年6月21日受賞 (所属は研究会発表当時)