国際共同研究

• 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

• 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

• 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

• 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

• 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

• 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

• Weight balancing on boundaries

  Luis Barba, Otfried Cheong, Michael Gene Dobbins, Rudolf Fleischer, Akitoshi Kawamura, Matias Korman, Yoshio Okamoto, János Pach, Yuan Tang, Takeshi Tokuyama, Sander Verdonschot

  Journal of Computational Geometry, Vol. 13, Article 44573, 2022

  DOI: 10.20382/jocg.v13i1a1

• 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

• 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

• Maximum properly colored trees in edge-colored graphs

  Jie Hu, Hao Li, Shun-ichi Maezawa

  Journal of Combinatorial Optimization, Vol. 44, pp. 154-171, 2022

  DOI: 10.1007/s10878-021-00824-z

• 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

• The Alon-Tarsi number of K5-minor-free graphs

  Toshiki Abe, Seog-Jin Kim, Kenta Ozeki

  Discrete Mathematics, Vol. 345, pp. 112764, 2022

  DOI: 10.1016/j.disc.2021.112764

• 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

• Approximability of monotone submodular function maximization under cardinality and matroid constraints in the streaming model

  Chien-Chung Huang, Naonori Kakimura, Simon Mauras, Yuichi Yoshida

  SIAM Journal on Discrete Mathematics, Vol. 36, pp. 355-382, 2022

  DOI: 10.1137/20M1357317

• 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

• 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

• Multi-pass streaming algorithms for monotone submodular function maximization

  Chien-Chung Huang, Naonori Kakimura

  Theory of Computing Systems, Vol. 66, pp. 354-394, 2022

  DOI: 10.1007/s00224-021-10065-6

• 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

• 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

• On the complexity of fair house allocation

  Naoyuki Kamiyama, Pasin Manurangsi, Warut Suksompong

  Operations Research Letters, Vol. 49, pp. 572-577, 2021

  DOI: 10.1016/j.orl.2021.06.006

• On 3-polytopes with non-Hamiltonian prisms

  Daiki Ikegami, Shun-ichi Maezawa, Carol T. Zamfirescu

  Journal of Graph Theory, Vol. 97, pp. 569-577, 2021

  DOI: 10.1002/jgt.22672

• Color number of cubic graphs having spanning tree with bounded number of leaves

  Analen A. Malnegro, Gina A. Malacas, Kenta Ozeki

  Theory and Applications of Graphs, Vol. 8, pp. Article 1, 2021

  DOI: 10.20429/tag.2021.080201

• 2-Factors of cubic bipartite graphs

  Nastaran Haghparast, Kenta Ozeki

  Discrete Mathematics, Vol. 344, pp. 112357, 2021

  DOI: 10.1016/j.disc.2021.112357

• ClusterSets: Optimizing planar clusters in categorical point data

  Jakob Geiger, Sabine Cornelsen, Jan-Henrik Haunert, Philipp Kindermann, Tamara Mchedlidze, Martin Nöllenburg, Yoshio Okamoto, Alexander Wolff

  Computer Graphics Forum, Vol. 40, pp. 471-481, 2021

  DOI: 10.1111/cgf.14322

• Market pricing for matroid rank valuations

  Kristof Berczi, Naonori Kakimura, Yusuke Kobayashi

  SIAM Journal on Discrete Mathematics, Vol. 35, pp. 2662-2678, 2021

  DOI: 10.1137/20M1386335

• 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