Activities

Publications and Awards

  • IPSJ-CS Outstanding Achievement and Contribution Award

    OKAMOTO, Yoshio (U. Electro-Communications)
    January 21, 2024

  • 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

  • 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

  • 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

  • A graph minor condition for graphs to be k-linked

    Shun-ichi Maezawa
    European Journal of Combinatorics, Vol. 116, Article 103874, 2024

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • Special case of Rota's basis conjecture on graphic matroids

    Shun-ichi Maezawa, Akiko Yazawa
    The Electronic Journal of Combinatorics, Vol. 29, Article P3.63, 2022

  • Characterization of (m,n)-linked planar graphs

    Kengo Enami, Shun-ichi Maezawa
    Graphs and Combinatorics, Vol. 38, pp. 131, 2022

  • 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

  • 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

  • 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

  • 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

  • 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

  • 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

  • Pareto efficient matchings with pairwise preferences

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

  • An even 2-factor in the line graph of a cubic graph

    SeungJae Eom, Kenta Ozeki
    Theory and Applications of Graphs, Vol. 9, Article 7, 2022

  • 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

  • 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

  • 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

  • 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

  • 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

  • Reconstructing phylogenetic trees from multipartite quartet systems

    Hiroshi Hirai, Yuni Iwamasa
    Algorithmica, Vol. 84, pp. 1875-1896, 2022

  • 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

  • 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

  • On the kernel of the surgery map restricted to the 1-loop part

    Yuta Nozaki, Masatoshi Sato, Masaaki Suzuki
    Journal of Topology, Vol. 15, pp. 587-619, 2022

  • 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

  • Linear-time recognition of double-threshold graphs

    Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno
    Algorithmica, Vol. 84, pp. 1163-1181, 2022

  • 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

  • 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

  • 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

  • Kempe equivalence classes of cubic graphs embedded on the projective plane

    Kenta Ozeki
    Combinatorica, Vol. 42, pp. 1451-1480, 2022

  • A combinatorial algorithm for computing the rank of a generic partitioned matrix with $2 \times 2$ submatrices

    Hiroshi Hirai, Yuni Iwamasa
    Mathematical Programming, Series A, Vol. 195, pp. 1-37, 2022

  • Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications

    Yuni Iwamasa, Kenjiro Takazawa
    Mathematical Programming, Series A, Vol. 194, pp. 229-256, 2022

  • 13th Research Award, the Operations Research Society of Japan

    KOBAYASHI, Yusuke (Kyoto U.)
    Sepetember 14, 2023

  • 12th Research Encourage Award, the Operations Research Society of Japan

    IWAMASA, Yuni (Kyoto U.)
    Sepetember 14, 2022

  • Submodular reassignment problem for reallocating agents to tasks with synergy effects

    Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
    Discrete Optimization, Vol. 44, pp. 100631, 2022

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

    Toshiki Abe, Seog-Jin Kim, Kenta Ozeki
    Discrete Mathematics, Vol. 345, pp. 112764, 2022

  • Covering projective planar graphs with three forests

    Raiji Mukae, Kenta Ozeki, Terukazu Sano, Ryuji Tazume
    Discrete Mathematics, Vol. 345, pp. 112748, 2022

  • 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

  • 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

  • A forbidden pair for connected graphs to have spanning k-trees

    Shun-ichi Maezawa, Kenta Ozeki
    Journal of Graph Theory, Vol. 99, pp. 509-519, 2022

  • 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

  • Multi-pass streaming algorithms for monotone submodular function maximization

    Chien-Chung Huang, Naonori Kakimura
    Theory of Computing Systems, Vol. 66, pp. 354-394, 2022

  • 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

  • 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

  • Proper colorings of plane quadrangulations without rainbow faces

    Kengo Enami, Kenta Ozeki, Tomoki Yamaguchi
    Graphs and Combinatorics, Vol. 37, pp. 1873-1890, 2021

  • 18th Young Scientists' Presentation Award, the Japan Society for Industrial and Applied Mathematics

    IWAMASA, Yuni (Kyoto U.)
    ”A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with 2×2 submatrices”
    June 17, 2022

  • 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

  • On the complexity of fair house allocation

    Naoyuki Kamiyama, Pasin Manurangsi, Warut Suksompong
    Operations Research Letters, Vol. 49, pp. 572-577, 2021

  • 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

  • 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

  • 2-Factors of cubic bipartite graphs

    Nastaran Haghparast, Kenta Ozeki
    Discrete Mathematics, Vol. 344, pp. 112357, 2021

  • 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

  • Algorithms for gerrymandering over graphs

    Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
    Theoretical Computer Science, Vol. 868, pp. 30-45, 2021

  • 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

  • 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

  • Market pricing for matroid rank valuations

    Kristof Berczi, Naonori Kakimura, Yusuke Kobayashi
    SIAM Journal on Discrete Mathematics, Vol. 35, pp. 2662-2678, 2021

  • 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

  • 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

  • 9th Hiroshi Fujiwara Encouragement Prize for Mathematical Science

    KOBAYASHI, Yusuke (Kyoto U.)
    "Study on efficient algorithms for combinatorial optimization problems"
    October 17, 2020