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

DAG-pathwidth: Graph algorithmic Analyses of DAG-type blockchain networks

Shoji Kasahara, Jun Kawahara, Shin-ichi Minato, Jumpei Mori

IEICE Transactions on Information and Systems, Vol. E106.D, pp. 272-283, 2023

DOI: 10.1587/transinf.2022FCP0007
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
Path cover problems with length cost

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

Algorithmica, Vol. 85, pp. 3348-3375, 2023

DOI: 10.1007/s00453-023-01106-2
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

DOI: 10.1007/978-3-031-43587-4_19
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
A spanning tree with at most $k$ leaves in a $K_{1,p}$-free graph

Kenta Ozeki, Masao Tsugaki

The Electronic Journal of Combinatorics, Vol. 30, Article 4.29, 2023

DOI: 10.37236/11698
Note on fair game edge-connectivity of graphs

Michitaka Furuya, Naoki Matsumoto, Yumiko Ohno, Kenta Ozeki

Discrete Applied Mathematics, Vol. 333, pp. 132-135, 2023

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

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

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

DOI: 10.4230/LIPIcs.ISAAC.2023.48
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
Feedback vertex set reconfiguration in planar graphs

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

Theoretical Computer Science, Vol. 979, Article 114188, 2023

DOI: 10.1016/j.tcs.2023.114188
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
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
Graphs with large total angular resolution

Oswin Aichholzer, Matias Korman, Yoshio Okamoto, Irene Parada, Daniel Perz, André van Renssen, Birgit Vogtenhuber

Theoretical Computer Science, Vol. 943, pp. 73-88, 2023

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

DOI: 10.1007/978-3-031-27051-2_24
Decremental optimization of vertex-coloring under the reconfiguration framework

Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

International Journal of Computer Mathematics: Computer Systems Theory, Vol. 8, pp. 80-92, 2023

DOI: 10.1080/23799927.2023.2185543
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
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

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

DOI: 10.5281/zenodo.7460388
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 2-bisection with small number of monochromatic edges of a claw-free cubic graph

Seungjae Eom, Kenta Ozeki

Graphs and Combinatorics, Vol. 39, Article 44944, 2023

DOI: 10.1007/s00373-023-02611-5
Arithmetic progressions, quasi progressions, and Gallai-Ramsey colorings

Yaping Mao, Kenta Ozeki, Aaron Robertson, Zhao Wang

Journal of Combinatorial Theory, Series A, Vol. 193, Article 105672, 2023

DOI: 10.1016/j.jcta.2022.105672
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
Pareto efficient matchings with pairwise preferences

Naoyuki Kamiyama

Theoretical Computer Science, Vol. 948, Article 113707, 2023

DOI: 10.1016/j.tcs.2023.113707
2023 Incentive Award, Minoru Ishida Foundation

SUZUKI, Akira (Tohoku U.)
October 27, 2023
13th Research Award, the Operations Research Society of Japan

KOBAYASHI, Yusuke (Kyoto U.)
Sepetember 14, 2023
XCSP3 Competition 2023, 2nd place of the Main CSP track

SOH, Takehide (Kobe U.), LE BERRE, Daniel (CRIL-CNRS), NABESHIMA, Hidetomo (Yamanashi U.), BANBARA, Mutsunori (Nagoya U.), TAMURA, Naoyuki (Kobe U.)
August 31, 2023
IPSJ Yamashita SIG Research Award for FY2022

WASA, Kunihiro (Hosei U.)

"Constant Amortized Time Enumeration of Eulerian trails (2021-AL-183)"

March 2, 2023

Publications and Awards

DAG-pathwidth: Graph algorithmic Analyses of DAG-type blockchain networks

Reconfiguration of colorings in triangulations of the sphere

Path cover problems with length cost

On computing a center persistence diagram

Sorting balls and water: Equivalence and computational complexity

A spanning tree with at most $k$ leaves in a $K_{1,p}$-free graph

Note on fair game edge-connectivity of graphs

Hamiltonian cycle reconfiguration with answer set programming

SAF: SAT-based attractor finder in asynchronous automata networks

Reconfiguration of the union of arborescences

Algorithmic theory of qubit routing

On reachable assignments under dichotomous preferences

Feedback vertex set reconfiguration in planar graphs

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

Reconfiguration of cliques in a graph

Sequentially swapping tokens: Further on graph classes

Graphs with large total angular resolution

Parameterized complexity of optimizing list vertex-coloring through reconfiguration

Decremental optimization of vertex-coloring under the reconfiguration framework

Happy set problem on subclasses of co-comparability graphs

ZDD-based algorithmic framework for solving shortest reconfiguration problems

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

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

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

A 2-bisection with small number of monochromatic edges of a claw-free cubic graph

Arithmetic progressions, quasi progressions, and Gallai-Ramsey colorings

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

Reconfiguring (non-spanning) arborescences

Pareto efficient matchings with pairwise preferences

2023 Incentive Award, Minoru Ishida Foundation

13th Research Award, the Operations Research Society of Japan

XCSP3 Competition 2023, 2nd place of the Main CSP track

IPSJ Yamashita SIG Research Award for FY2022