Conference| 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
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
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
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
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
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
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
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
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
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
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
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
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
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

DOI: 10.4204/EPTCS.372.21
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

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

Proc. of Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pp. 1342-1355, 2022

DOI: 10.1137/1.9781611977073.56
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
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

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

DOI: 10.1007/978-3-030-94676-0
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

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

Publications and Awards

Reallocation problems with minimum completion time

Reconfiguration of colorings in triangulations of the sphere

On computing a center persistence diagram

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

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

Sequentially swapping tokens: Further on graph classes

Extended MSO model checking via small vertex integrity

On reachable assignments under dichotomous preferences

Parameterized complexity of optimizing list vertex-coloring through reconfiguration

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

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

Algorithms for coloring reconfiguration under recolorability digraphs

Sorting balls and water: Equivalence and computational complexity

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

Independent set reconfiguration on directed graphs

Quantaloidal approach to constraint satisfaction

Unlabeled multi-robot motion planning with tighter separation bounds

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

Reforming an envy-free matching

Online task assignment problems with reusable resources

Computing diverse shortest paths efficiently: A theoretical and experimental study

Finding diverse trees, paths, and more

Reconfiguration of regular induced subgraphs

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

Distributed reconfiguration of spanning trees

Computational complexity of jumping block puzzles

Reconfiguring directed trees in a digraph

Decremental optimization of vertex-coloring under the reconfiguration framework

Locating evacuation centers optimally in path and cycle networks

Dynamic bipartite matching market with arrivals and departures

Finding diverse trees, paths, and more

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

Exploring the gap between treedepth and vertex cover through vertex integrity

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