Activities

Publications and Awards

  • Reallocation problems with minimum completion time

    Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono
    Proc. of 28th International Computing and Combinatorics Conference (COCOON 2022), Lecture Notes in Computer Science, Vol. 13595, pp. 292-304, 2022

  • 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

  • On computing a center persistence diagram

    Yuya Higashikawa, Naoki Katoh, Guohui Lin, Eiji Miyano, Suguru Tamaki, Junichi Teruyama, Binhai Zhu
    Proc. of 24th International Symposium on Fundamentals of Computation Theory (FCT 2023), Lecture Notes in Computer Science, Vol. 14292, pp. 262-275, 2023

  • Hamiltonian cycle reconfiguration with answer set programming

    Takahiro Hirate, Mutsunori Banbara, Katsumi Inoue, Xiao-Nan Lu, Hidetomo Nabeshima, Torsten Schaub, Takehide Soh, Naoyuki Tamura
    Proc. of 18th European Conference on Logics in Artificial Intelligence (JELIA 2023), Lecture Notes in Artificial Intelligence, Vol. 14238, pp. 262-277, 2023

  • SAF: SAT-based attractor finder in asynchronous automata networks

    Takehide Soh, Morgan Magnin, Daniel Le Berre, Mutsunori Banbara, Naoyuki Tamura
    Proc. of 21st International Conference on Computational Methods in Systems Biology (CMSB 2023), Lecture Notes in Bioinformatics, Vol. 14173, pp. 175-183, 2023

  • Reconfiguration of the union of arborescences

    Yusuke Kobayashi, Ryoga Mahara, Tamás Schwarcz
    Proc. of 34th International Symposium on Algorithms and Computation (ISAAC 2023), Leibniz International Proceedings in Informatics, Vol. 283, pp. 48:1-48:14, 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

  • 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

  • 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

  • Parameterized complexity of optimizing list vertex-coloring through reconfiguration

    Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou
    Proc. of 17th International Conference and Workshops on Algorithms and Computation (WALCOM 2023), Lecture Notes in Computer Science, Vol. 13973, pp. 279-290, 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

  • Efficient non-isomorphic graph enumeration algorithms for subclasses of perfect graphs

    Jun Kawahara, Toshiki Saitoh, Hirokazu Takeda, Ryo Yoshinaka, Yui Yoshioka
    Proc. of 17th International Conference and Workshops on Algorithms and Computation (WALCOM 2023), Lecture Notes in Computer Science, Vol. 13973, pp. 151-163, 2023

  • SAT-based method for finding attractors in asynchronous multi-valued networks

    Takehide Soh, Morgan Magnin, Daniel Le Berre, Mutsunori Banbara, Naoyuki Tamura
    Proc. of 16th International Joint Conference on Biomedical Enginnering Systems and Technologies, Vol. hal-03964870, 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

  • Algorithms for coloring reconfiguration under recolorability digraphs

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Akira Suzuki
    Proc. of 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz International Proceedings in Informatics, Vol. 248, pp. 4:1–4:19, 2022

  • 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

  • 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

  • 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

  • Quantaloidal approach to constraint satisfaction

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura
    Proc. of 4th International Conference on Applied Category Theory (ACT 2021), Electronic Proceedings in Theoretical Computer Science, Vol. 372, pp. 289-305, 2022

  • Unlabeled multi-robot motion planning with tighter separation bounds

    Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, Stijn Slot
    Proc. of 38th International Symposium on Computational Geometry (SoCG 2022), Leibniz International Proceedings in Informatics, Vol. 224, pp. 12:1-12:16, 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

  • 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

  • Online task assignment problems with reusable resources

    Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
    Proc. of 36th AAAI Conference on Artificial Intelligence (AAAI 2022), Vol. 36, pp. 5199-5207, 2021

  • 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

  • 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

  • Path cover problems with length cost

    Kenya Kobayashi, Guohui Lin, Eiji Miyano, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, Tsuyoshi Yagita
    Proc. of 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), Lecture Notes in Computer Science, Vol. 13174, pp. 396-408, 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

  • 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

  • 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

  • Decremental optimization of vertex-coloring under the reconfiguration framework

    Yusuke Yanagisawa, Yuma Tamura, Akira Suzuki, Xiao Zhou
    Proc. of 27th International Computing and Combinatorics Conference (COCOON 2021), Lecture Notes in Computer Science, Vol. 13025, pp. 355-366, 2021

  • Locating evacuation centers optimally in path and cycle networks

    Robert Benkoczi, Binay Bhattacharya, Yuya Higashikawa, Tsunehiko Kameda, Naoki Katoh, Junichi Teruyama
    Proc. of 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021), Open Access Series in Informatics, Vol. 96, pp. 13:1-13:19, 2021

  • Dynamic bipartite matching market with arrivals and departures

    Naonori Kakimura, Donghao Zhu
    Proc. of 17th Conference on Web and Internet Economics (WINE 2021), Lecture Notes in Computer Science, Vol. 13112, pp. 544, 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: 

  • A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with $2 \time 2$ submatrices

    Yuni Iwamasa
    Proc. of 22nd Conference on Integer Programming and Combinatorial Optimization (IPCO 2021), Lecture Notes in Computer Science, Vol. 12707, pp. 119-133, 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

  • Minmax regret 1-sink location problems on dynamic flow path networks with parametric weights

    Tetsuya Fujie, Yuya Higashikawa, Naoki Katoh, Junichi Teruyama, Yuki Tokuni
    Proc. of 15th International Conference and Workshops on Algorithms and Computation (WALCOM 2021), Lecture Notes in Computer Science, Vol. 12635, pp. 52-64, 2021