2021| KAKENHI Grant-in-Aid for Transformative Research Areas (B)

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

DOI: 10.1016/j.dam.2021.06.004
Low-congestion shortcut and graph parameters

Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi

Distributed Computing, Vol. 34, pp. 349-365, 2021

DOI: 10.1007/s00446-021-00401-x
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
Proper colorings of plane quadrangulations without rainbow faces

Kengo Enami, Kenta Ozeki, Tomoki Yamaguchi

Graphs and Combinatorics, Vol. 37, pp. 1873-1890, 2021

DOI: 10.1007/s00373-021-02350-5
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
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

DOI: 10.1587/transfun.2020DMP0003
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
Longest common subsequence in sublinear space

Masashi Kiyomi, Takashi Horiyama, Yota Otachi

Information Processing Letters, Vol. 168, pp. 106084, 2021

DOI: 10.1016/j.ipl.2020.106084
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
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

DOI: 10.1016/j.tcs.2021.05.008
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

DOI: 10.1016/j.tcs.2021.05.003
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

DOI: 10.1016/j.tcs.2021.04.023
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

DOI: 10.1016/j.tcs.2021.03.037
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
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

DOI: 10.1016/j.tcs.2021.03.006
Optimal reconfiguration of optimal ladder lotteries

Katsuhisa Yamanaka, Takashi Horiyama, Kunihiro Wasa

Theoretical Computer Science, Vol. 859, pp. 57-69, 2021

DOI: 10.1016/j.tcs.2021.01.009
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
Trichotomy for the reconfiguration problem of integer linear systems

Kei Kimura, Akira Suzuki

Theoretical Computer Science, Vol. 856, pp. 88-109, 2021

DOI: 10.1016/j.tcs.2020.12.025
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
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

DOI: 10.1016/j.tcs.2020.10.026
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)

Publications and Awards

Online task assignment problems with reusable resources

Decrease and reset for power-down

Finding diverse trees, paths, and more

On the security number of the Cartesian product of graphs

Distributed reconfiguration of spanning trees

Efficient enumeration of dominating sets for sparse graphs

Low-congestion shortcut and graph parameters

Computational complexity of jumping block puzzles

Reconfiguring directed trees in a digraph

Decremental optimization of vertex-coloring under the reconfiguration framework

Proper colorings of plane quadrangulations without rainbow faces

Locating evacuation centers optimally in path and cycle networks

Dynamic bipartite matching market with arrivals and departures

Max-min 3-dispersion problems

On the complexity of fair house allocation

On 3-polytopes with non-Hamiltonian prisms

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

2-Factors of cubic bipartite graphs

Longest common subsequence in sublinear space

ClusterSets: Optimizing planar clusters in categorical point data

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

Almost linear time algorithms for minsum k-sink problems on dynamic flow path networks

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

Finding diverse trees, paths, and more

Algorithms for gerrymandering over graphs

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

Finding a maximum minimal separator: Graph classes and fixed-parameter tractability

Optimal reconfiguration of optimal ladder lotteries

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

Trichotomy for the reconfiguration problem of integer linear systems

Market pricing for matroid rank valuations

Computing the largest bond and the maximum connected cut of a graph

Approximability of the independent feedback vertex set problem for bipartite graphs

FIT2020 Funai Best Paper Award

2021 JSAI Incentive Award, the Japanese Society for Artificial Intelligence