A01| KAKENHI Grant-in-Aid for Transformative Research Areas (B)

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

DOI: 10.4230/LIPIcs.SoCG.2023.43
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

DOI: j.tcs.2023.114158
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

DOI: 10.1007/978-3-031-38906-1_35
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

DOI: 10.1016/j.tcs.2023.114196
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

DOI: 10.1007/s00453-023-01117-z
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

DOI: 10.1016/j.tcs.2023.113863
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

DOI: 10.1007/978-3-031-34347-6_28
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

DOI: 10.4230/LIPIcs.ICALP.2023.81
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

DOI: 10.4230/LIPIcs.MFCS.2023.58
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

DOI: 10.1007/978-3-031-38906-1_34
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

DOI: 10.1007/978-3-031-27051-2_17
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

DOI: 10.1587/transfun.2021DMP0017
Reconfiguration of cliques in a graph

Takehiro Ito, Hirotaka Ono, Yota Otachi

Discrete Applied Mathematics, Vol. 333, pp. 43-58, 2023

DOI: 10.1016/j.dam.2023.01.026
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

DOI: 10.1007/978-3-031-23101-8_15
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

DOI: 10.4230/LIPIcs.ISAAC.2022.20
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

DOI: 10.1007/978-3-031-21203-1_43
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

DOI: 10.1007/s00453-022-01081-0
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

DOI: 10.1007/978-3-031-33271-5_12
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

DOI: 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 Otachi

Proc. of 37th AAAI Conference on Artificial Intelligence (AAAI 2023), AAAI-23 Technical Tracks 4, Vol. 37, pp. 3968-3976, 2023

DOI: 10.1609/aaai.v37i4.25511
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

DOI: 10.1016/j.tcs.2022.12.007
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

DOI: 10.4230/LIPIcs.FUN.2022.16
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

DOI: 10.1016/j.orl.2022.05.001
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

DOI: 10.1007/s00224-022-10076-x
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

DOI: 10.4230/LIPIcs.MFCS.2022.6
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

DOI: 10.4230/LIPIcs.ESA.2022.61
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

DOI: 10.1007/978-3-031-15914-5_25
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

DOI: 10.1145/3517804.3524148
Constant amortized time enumeration of Eulerian trails

Kazuhiro Kurita, Kuniihiro Wasa

Theoretical Computer Science, Vol. 923, Article 44573, 2022

DOI: 10.1016/j.tcs.2022.04.048
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

DOI: 10.4230/LIPIcs.MFCS.2022.58
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

DOI: 10.1137/20M1364370
Parameterized complexity of graph burning

Yasuaki Kobayashi, Yota Otachi

Algorithmica, Vol. 84, pp. 2379-2393, 2022

DOI: 10.1007/s00453-022-00962-8
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

DOI: 10.1137/1.9781611977073.56
Linear-time recognition of double-threshold graphs

Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno

Algorithmica, Vol. 84, pp. 1163-1181, 2022

DOI: 10.1007/s00453-021-00921-9
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

DOI: 10.1609/aaai.v36i5.20441
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

DOI: 10.1609/aaai.v36i4.20290
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: 10.1609/aaai.v35i5.16495
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 Otachi

Algorithmica, Vol. 84, pp. 871-895, 2022

DOI: 10.1007/s00453-021-00875-y
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

DOI: 10.1007/978-3-030-96731-4_4
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

DOI: 10.1007/978-3-030-96731-4_13
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

DOI: 10.4230/LIPIcs.STACS.2022.15
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

DOI: 10.1587/transinf.2021FCP0013
On the security number of the Cartesian product of graphs

Marko Jakovac, Yota Otachi

Discrete Applied Mathematics, Vol. 304, pp. 119-128, 2021

DOI: 10.1016/j.dam.2021.07.030
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

DOI: 10.1007/978-3-030-91081-5_40
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

DOI: 10.1016/j.dam.2021.06.004
Low-congestion shortcut and graph parameters

Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi

Distributed Computing, Vol. 34, pp. 349-365, 2021

DOI: 10.1007/s00446-021-00401-x
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

DOI: 10.1007/978-3-030-89543-3_54
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

DOI: 10.1007/978-3-030-89543-3_29
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

DOI: 10.1587/transfun.2020DMP0003
Longest common subsequence in sublinear space

Masashi Kiyomi, Takashi Horiyama, Yota Otachi

Information Processing Letters, Vol. 168, pp. 106084, 2021

DOI: 10.1016/j.ipl.2020.106084
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

DOI: 10.1016/j.tcs.2021.05.008
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

DOI: 10.1016/j.tcs.2021.04.023
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

DOI: 10.1016/j.tcs.2021.03.037
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

DOI: 10.1007/978-3-030-75242-2_19
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

DOI: 10.1016/j.tcs.2021.03.006
Optimal reconfiguration of optimal ladder lotteries

Katsuhisa Yamanaka, Takashi Horiyama, Kunihiro Wasa

Theoretical Computer Science, Vol. 859, pp. 57-69, 2021

DOI: 10.1016/j.tcs.2021.01.009
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

DOI: 10.1007/s00453-020-00789-1
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

DOI: 10.1016/j.tcs.2020.10.026
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)

Publications and Awards

Reconfiguration of colorings in triangulations of the sphere

Sorting balls and water: Equivalence and computational complexity

Algorithmic theory of qubit routing

On reachable assignments under dichotomous preferences

Reconfiguration of spanning trees with degree constraints or diameter constraints

Fixed-parameter algorithms for graph constraint logic

Reconfiguration and enumeration of optimal cyclic ladder lotteries

Rerouting planar curves and disjoint paths

Polynomial-delay enumeration of large maximal common independent sets in two matroids

Reconfiguration of time-respecting arborescences

Reconfiguration of vertex-disjoint shortest paths on graphs

Approximability of the distance independent set problem on regular graphs and planar graphs

Reconfiguration of cliques in a graph

Sequentially swapping tokens: Further on graph classes

Extended MSO model checking via small vertex integrity

On reachable assignments under dichotomous preferences

Happy set problem on subclasses of co-comparability graphs

ZDD-based algorithmic framework for solving shortest reconfiguration problems

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

A framework to design approximation algorithms for finding diverse solutions in combinatorial problems

Reconfiguring (non-spanning) arborescences

Sorting balls and water: Equivalence and computational complexity

A parameterized view to the robust recoverable base problem of matroids under structural uncertainty

An improved deterministic parameterized algorithm for cactus vertex deletion

Parameterized complexity of non-separating and non-disconnecting paths and sets

Algorithmic meta-theorems for combinatorial reconfiguration revisited

Polynomial-delay and polynomial-space enumeration of large maximal matchings

Linear-delay enumeration for minimal Steiner problems

Constant amortized time enumeration of Eulerian trails

Independent set reconfiguration on directed graphs

Shortest reconfiguration of perfect matchings via alternating cycles

Parameterized complexity of graph burning

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

Linear-time recognition of double-threshold graphs

Reforming an envy-free matching

Computing diverse shortest paths efficiently: A theoretical and experimental study

Finding diverse trees, paths, and more

IPSJ Yamashita SIG Research Award for FY2022

Parameterized complexity of (A, l)-path packing

Reconfiguration of regular induced subgraphs

Happy set problem on subclasses of co-comparability graphs

Reconfiguration of spanning trees with degree constraint or diameter constraint

An O(n^2)-time algorithm for computing a max-min 3-dispersion on a point set in convex position

On the security number of the Cartesian product of graphs

Distributed reconfiguration of spanning trees

Efficient enumeration of dominating sets for sparse graphs

Low-congestion shortcut and graph parameters

Computational complexity of jumping block puzzles

Reconfiguring directed trees in a digraph

Max-min 3-dispersion problems

Longest common subsequence in sublinear space

A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number

A (probably) optimal algorithm for bisection on bounded-treewidth graphs

Finding diverse trees, paths, and more

Algorithms for gerrymandering over graphs

Exploring the gap between treedepth and vertex cover through vertex integrity

Finding a maximum minimal separator: Graph classes and fixed-parameter tractability

Optimal reconfiguration of optimal ladder lotteries

Computing the largest bond and the maximum connected cut of a graph

Approximability of the independent feedback vertex set problem for bipartite graphs

FIT2020 Funai Best Paper Award

2021 JSAI Incentive Award, the Japanese Society for Artificial Intelligence