Activities

Publications and Awards

  • 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

  • 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

  • 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

  • On the security number of the Cartesian product of graphs

    Marko Jakovac, Yota Otachi
    Discrete Applied Mathematics, Vol. 304, pp. 119-128, 2021

  • 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

  • Efficient enumeration of dominating sets for sparse graphs

    Kazuhiro Kurita, Kunihiro Wasa, Hiroki Arimura, Takeaki Uno
    Discrete Applied Mathematics, Vol. 303, pp. 283-295, 2021

  • Low-congestion shortcut and graph parameters

    Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi
    Distributed Computing, Vol. 34, pp. 349-365, 2021

  • 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

  • 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

  • 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

  • Proper colorings of plane quadrangulations without rainbow faces

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

  • 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

  • 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

  • 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

  • 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

  • Longest common subsequence in sublinear space

    Masashi Kiyomi, Takashi Horiyama, Yota Otachi
    Information Processing Letters, Vol. 168, pp. 106084, 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

  • A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number

    Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki Arimura
    Theoretical Computer Science, Vol. 874, pp. 32-41, 2021

  • 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

  • A (probably) optimal algorithm for bisection on bounded-treewidth graphs

    Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone
    Theoretical Computer Science, Vol. 873, pp. 38-46, 2021

  • 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: 

  • 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

  • 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

  • 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

  • Optimal reconfiguration of optimal ladder lotteries

    Katsuhisa Yamanaka, Takashi Horiyama, Kunihiro Wasa
    Theoretical Computer Science, Vol. 859, pp. 57-69, 2021

  • 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

  • Trichotomy for the reconfiguration problem of integer linear systems

    Kei Kimura, Akira Suzuki
    Theoretical Computer Science, Vol. 856, pp. 88-109, 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

  • Approximability of the independent feedback vertex set problem for bipartite graphs

    Yuma Tamura, Takehiro Ito, Xiao Zhou
    Theoretical Computer Science, Vol. 849, pp. 227-236, 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

  • 2021 JSAI Incentive Award, the Japanese Society for Artificial Intelligence

    HANAKA, Tesshu (Chuo U.), KOBAYASHI, Yasuaki (Kyoto U.), KURITA, Kazuhiro (National Institute of Informatics), OTACHI, Yota (Nagoya U.)
    "Algorithms for finding diverse subgraphs"
    June 21, 2021 (Affiliation at the time of the presentation)