Publications and Awards
-
Online task assignment problems with reusable resources
Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, Ken-ichi KawarabayashiProc. 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 KawaharaEnergy Systems, Vol. 14, pp. 445-471, 2021 -
Finding diverse trees, paths, and more
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota OtachiProc. 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 OtachiDiscrete Applied Mathematics, Vol. 304, pp. 119-128, 2021 -
Distributed reconfiguration of spanning trees
Yukiko Yamauchi, Naoyuki Kamiyama, Yota OtachiProc. 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 UnoDiscrete Applied Mathematics, Vol. 303, pp. 283-295, 2021 -
Low-congestion shortcut and graph parameters
Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke IzumiDistributed Computing, Vol. 34, pp. 349-365, 2021 -
Computational complexity of jumping block puzzles
Masaaki Kanzaki, Yota Otachi, Ryuhei UeharaProc. 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 WasaProc. 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 ZhouProc. 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 YamaguchiGraphs 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 TeruyamaProc. 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 ZhuProc. 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 WasaIEICE 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 SuksompongOperations Research Letters, Vol. 49, pp. 572-577, 2021 -
On 3-polytopes with non-Hamiltonian prisms
Daiki Ikegami, Shun-ichi Maezawa, Carol T. ZamfirescuJournal of Graph Theory, Vol. 97, pp. 569-577, 2021DOI: 10.1002/jgt.22672 -
Color number of cubic graphs having spanning tree with bounded number of leaves
Analen A. Malnegro, Gina A. Malacas, Kenta OzekiTheory and Applications of Graphs, Vol. 8, pp. Article 1, 2021 -
2-Factors of cubic bipartite graphs
Nastaran Haghparast, Kenta OzekiDiscrete Mathematics, Vol. 344, pp. 112357, 2021 -
Longest common subsequence in sublinear space
Masashi Kiyomi, Takashi Horiyama, Yota OtachiInformation 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 WolffComputer Graphics Forum, Vol. 40, pp. 471-481, 2021DOI: 10.1111/cgf.14322 -
A constant amortized time enumeration algorithm for independent sets in graphs with bounded clique number
Kazuhiro Kurita, Kunihiro Wasa, Takeaki Uno, Hiroki ArimuraTheoretical 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 WataseTheoretical Computer Science, Vol. 873, pp. 87-113, 2021 -
A (probably) optimal algorithm for bisection on bounded-treewidth graphs
Tesshu Hanaka, Yasuaki Kobayashi, Taiga SoneTheoretical Computer Science, Vol. 873, pp. 38-46, 2021 -
Finding diverse trees, paths, and more
Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota OtachiProc. of the AAAI Conference on Artificial Intelligence (AAAI 2021), Vol. 35, pp. 3778-3786, 2021DOI: -
Algorithms for gerrymandering over graphs
Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio OkamotoTheoretical 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 IwamasaProc. 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 OtachiProc. 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 YagitaTheoretical Computer Science, Vol. 865, pp. 131-140, 2021 -
Optimal reconfiguration of optimal ladder lotteries
Katsuhisa Yamanaka, Takashi Horiyama, Kunihiro WasaTheoretical 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 TokuniProc. 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 SuzukiTheoretical Computer Science, Vol. 856, pp. 88-109, 2021 -
Market pricing for matroid rank valuations
Kristof Berczi, Naonori Kakimura, Yusuke KobayashiSIAM Journal on Discrete Mathematics, Vol. 35, pp. 2662-2678, 2021DOI: 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. SouzaAlgorithmica, Vol. 83, pp. 1421-1458, 2021 -
Approximability of the independent feedback vertex set problem for bipartite graphs
Yuma Tamura, Takehiro Ito, Xiao ZhouTheoretical 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)