Publications and Awards
-
Reconfiguration of colorings in triangulations of the sphere
Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta OzekiProc. 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 YoshinakaTheoretical Computer Science, Vol. 978, Article 114158, 2023DOI: j.tcs.2023.114158 -
Algorithmic theory of qubit routing
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio OkamotoProc. 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 OzekiTheoretical 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 WasaAlgorithmica, 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 SuzukiTheoretical Computer Science, Vol. 959, Article 113863, 2023 -
Reconfiguration and enumeration of optimal cyclic ladder lotteries
Yuta Nozaki, Katsuhisa Yamanaka, Kunihiro WasaProc. 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 OzekiProc. 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 WasaProc. 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 SuzukiProc. 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 UeharaProc. 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 MiyanoIEICE 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 OtachiDiscrete Applied Mathematics, Vol. 333, pp. 43-58, 2023 -
Sequentially swapping tokens: Further on graph classes
Hironori Kiya, Yuto Okada, Hirotaka Ono, Yota OtachiProc. 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 OtachiProc. 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 OzekiProc. 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 TamuraAlgorithmica, 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 TodaProc. 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 OzekiACM Transactions on Algorithms, Vol. 19, Article 6, 2023DOI: 10.1145/3561302 -
A framework to design approximation algorithms for finding diverse solutions in combinatorial problems
Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota OtachiProc. 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 WasaTheoretical 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 YoshinakaProc. 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 OkamotoOperations 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 OtachiTheory 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 SaurabhProc. 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 OtachiProc. 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 WasaProc. 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 WasaProc. 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 WasaTheoretical 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 WasaProc. 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 OkamotoSIAM Journal on Discrete Mathematics, Vol. 36, pp. 1102-1123, 2022DOI: 10.1137/20M1364370 -
Parameterized complexity of graph burning
Yasuaki Kobayashi, Yota OtachiAlgorithmica, 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 OzekiProc. 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 UnoAlgorithmica, 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 OzekiProc. 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 OtachiProc. 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 OtachiProc. of the AAAI Conference on Artificial Intelligence (AAAI 2021), Vol. 35, pp. 3778-3786, 2021 -
IPSJ Yamashita SIG Research Award for FY2022
WASA, Kunihiro (Hosei U.)"Constant Amortized Time Enumeration of Eulerian trails (2021-AL-183)"March 2, 2023 -
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 OtachiAlgorithmica, Vol. 84, pp. 871-895, 2022 -
Reconfiguration of regular induced subgraphs
Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, Kunihiro WasaProc. 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 TamuraProc. 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 WasaProc. 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 YamanakaIEICE 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 OtachiDiscrete Applied Mathematics, Vol. 304, pp. 119-128, 2021 -
Distributed reconfiguration of spanning trees
Yukiko Yamauchi, Naoyuki Kamiyama, Yota OtachiProc. 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 UnoDiscrete Applied Mathematics, Vol. 303, pp. 283-295, 2021 -
Low-congestion shortcut and graph parameters
Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke IzumiDistributed Computing, Vol. 34, pp. 349-365, 2021 -
Computational complexity of jumping block puzzles
Masaaki Kanzaki, Yota Otachi, Ryuhei UeharaProc. 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 WasaProc. 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 WasaIEICE 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 OtachiInformation 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 ArimuraTheoretical Computer Science, Vol. 874, pp. 32-41, 2021 -
A (probably) optimal algorithm for bisection on bounded-treewidth graphs
Tesshu Hanaka, Yasuaki Kobayashi, Taiga SoneTheoretical Computer Science, Vol. 873, pp. 38-46, 2021 -
Finding diverse trees, paths, and more
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota OtachiProc. of the AAAI Conference on Artificial Intelligence (AAAI 2021), Vol. 35, pp. 3778-3786, 2021DOI: -
Algorithms for gerrymandering over graphs
Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio OkamotoTheoretical 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 OtachiProc. 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 YagitaTheoretical Computer Science, Vol. 865, pp. 131-140, 2021 -
Optimal reconfiguration of optimal ladder lotteries
Katsuhisa Yamanaka, Takashi Horiyama, Kunihiro WasaTheoretical 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. SouzaAlgorithmica, Vol. 83, pp. 1421-1458, 2021 -
Approximability of the independent feedback vertex set problem for bipartite graphs
Yuma Tamura, Takehiro Ito, Xiao ZhouTheoretical Computer Science, Vol. 849, pp. 227-236, 2021 -
FIT2020 Funai Best Paper Award
OKAMOTO, Yoshio (U. Electro-Communications), ITO, Takehiro (Tohoku U.), KAKIMURA, Naonori (Keio U.), KAMIYAMA, Naoyuki (Kyushu U.), KOBAYASHI, Yusuke (Kyoto U.)"Fixed-parameter algorithms for the robust recoverable base problem of matroids under structural uncertainty"August 26, 2021 -
2021 JSAI Incentive Award, the Japanese Society for Artificial Intelligence
HANAKA, Tesshu (Chuo U.), KOBAYASHI, Yasuaki (Kyoto U.), KURITA, Kazuhiro (National Institute of Informatics), OTACHI, Yota (Nagoya U.)"Algorithms for finding diverse subgraphs"June 21, 2021 (Affiliation at the time of the presentation)