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

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

DOI: 10.1007/978-3-031-22105-7_26
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
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
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
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 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
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
On robustness against evacuees' unexpected movement in automatic evacuation guiding

Jun Kawahara, Takanori Hara, Masahiro Sasabe

Computers and Electrical Engineering, Vol. 105, Article 108531, 2022

DOI: 10.1016/j.compeleceng.2022.108531
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
A satisfiability algorithm for deterministic width-2 branching programs

Tomu Makita, Atsuki Nagao, Tatsuki Okada, Kazuhisa Seto, Junichi Teruyama

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E105-A, pp. 1298-1308, 2022

DOI: 10.1587/transfun.2021EAP1120
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
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

DOI: 10.4230/LIPIcs.ISAAC.2022.4
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
Reconfiguring k-path vertex covers

Duc A. Hoang, Akira Suzuki, Tsuyoshi Yagita

IEICE Transactions on Information and Systems, Vol. E105-D, pp. 1258-1272, 2022

DOI: 10.1587/transinf.2021EDP7177
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
Decrease and reset for power-down

James Andro-Vasko, Wolfgang Bein, Hiro Ito, Shoji Kasahara, Jun Kawahara

Energy Systems, Vol. 14, pp. 445-471, 2021

DOI: 10.1007/s12667-021-00475-3
2023 Incentive Award, Minoru Ishida Foundation

SUZUKI, Akira (Tohoku U.)
October 27, 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
XCSP3 Competition 2022, 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 3, 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

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

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

DOI: 10.4230/OASIcs.ATMOS.2021.13
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
Almost linear time algorithms for minsum k-sink problems on dynamic flow path networks

Yuya Higashikawa, Naoki Katoh, Junichi Teruyama, Koji Watase

Theoretical Computer Science, Vol. 873, pp. 87-113, 2021

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

DOI: 10.1007/978-3-030-68211-8_5
Trichotomy for the reconfiguration problem of integer linear systems

Kei Kimura, Akira Suzuki

Theoretical Computer Science, Vol. 856, pp. 88-109, 2021

DOI: 10.1016/j.tcs.2020.12.025
20th LA/EATCS-Japan Presentation Award

KAWAHARA, Jun (Kyoto U.)

"On an efficient solver for combinatorial reconfiguration problems using ZDDs"

Authors: ITO, Takehiro (Tohoku U.), KAWAHARA, Jun (Kyoto U.), SOH, Takehide (Kobe U.), SUZUKI, Akira (Tohoku U.), TERUYAMA, Junichi (U. Hyogo), TODA, Takahisa (U. Electro-Communications)

February 3, 2022

Publications and Awards

Reallocation problems with minimum completion time

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

Path cover problems with length cost

On computing a center persistence diagram

Sorting balls and water: Equivalence and computational complexity

Hamiltonian cycle reconfiguration with answer set programming

SAF: SAT-based attractor finder in asynchronous automata networks

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 of time-respecting arborescences

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

On robustness against evacuees' unexpected movement in automatic evacuation guiding

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

A satisfiability algorithm for deterministic width-2 branching programs

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

Algorithms for coloring reconfiguration under recolorability digraphs

Reconfiguring (non-spanning) arborescences

Sorting balls and water: Equivalence and computational complexity

Reconfiguring k-path vertex covers

Independent set reconfiguration on directed graphs

Decrease and reset for power-down

2023 Incentive Award, Minoru Ishida Foundation

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

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

Path cover problems with length cost

Happy set problem on subclasses of co-comparability graphs

Reconfiguration of spanning trees with degree constraint or diameter constraint

Decremental optimization of vertex-coloring under the reconfiguration framework

Locating evacuation centers optimally in path and cycle networks

Max-min 3-dispersion problems

Almost linear time algorithms for minsum k-sink problems on dynamic flow path networks

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

Trichotomy for the reconfiguration problem of integer linear systems

20th LA/EATCS-Japan Presentation Award