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

DAG-pathwidth: Graph algorithmic Analyses of DAG-type blockchain networks

Shoji Kasahara, Jun Kawahara, Shin-ichi Minato, Jumpei Mori

IEICE Transactions on Information and Systems, Vol. E106.D, pp. 272-283, 2023

DOI: 10.1587/transinf.2022FCP0007
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
Sorting balls and water: Equivalence and computational complexity

Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka

Theoretical Computer Science, Vol. 978, Article 114158, 2023

DOI: j.tcs.2023.114158
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

DOI: 10.37236/11698
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

DOI: 10.1016/j.dam.2023.03.024
A graph minor condition for graphs to be k-linked

Shun-ichi Maezawa

European Journal of Combinatorics, Vol. 116, Article 103874, 2024

DOI: 10.1016/j.ejc.2023.103874
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

DOI: 10.1016/j.tcs.2023.114196
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
Approximability of the distance independent set problem on regular graphs and planar graphs

Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E105-A, pp. 1211-1222, 2022

DOI: 10.1587/transfun.2021DMP0017
Reconfiguration of cliques in a graph

Takehiro Ito, Hirotaka Ono, Yota Otachi

Discrete Applied Mathematics, Vol. 333, pp. 43-58, 2023

DOI: 10.1016/j.dam.2023.01.026
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
Decremental optimization of vertex-coloring under the reconfiguration framework

Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao Zhou

International Journal of Computer Mathematics: Computer Systems Theory, Vol. 8, pp. 80-92, 2023

DOI: 10.1080/23799927.2023.2185543
Happy set problem on subclasses of co-comparability graphs

Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura

Algorithmica, Vol. 85, Article 44947, 2023

DOI: 10.1007/s00453-022-01081-0
On robustness against evacuees' unexpected movement in automatic evacuation guiding

Jun Kawahara, Takanori Hara, Masahiro Sasabe

Computers and Electrical Engineering, Vol. 105, Article 108531, 2022

DOI: 10.1016/j.compeleceng.2022.108531
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

DOI: 10.37236/10835
Characterization of (m,n)-linked planar graphs

Kengo Enami, Shun-ichi Maezawa

Graphs and Combinatorics, Vol. 38, pp. 131, 2022

DOI: 10.1007/s00373-022-02537-4
A satisfiability algorithm for deterministic width-2 branching programs

Tomu Makita, Atsuki Nagao, Tatsuki Okada, Kazuhisa Seto, Junichi Teruyama

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E105-A, pp. 1298-1308, 2022

DOI: 10.1587/transfun.2021EAP1120
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

DOI: 10.1145/3561302
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

DOI: 10.1007/s00373-023-02611-5
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
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

DOI: 10.1016/j.tcs.2022.12.007
Pareto efficient matchings with pairwise preferences

Naoyuki Kamiyama

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

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

DOI: 10.20429/tag.2022.090107
Reconfiguring k-path vertex covers

Duc A. Hoang, Akira Suzuki, Tsuyoshi Yagita

IEICE Transactions on Information and Systems, Vol. E105-D, pp. 1258-1272, 2022

DOI: 10.1587/transinf.2021EDP7177
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
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

DOI: 10.1016/j.orl.2022.05.001
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

DOI: 10.1007/s00224-022-10076-x
Constant amortized time enumeration of Eulerian trails

Kazuhiro Kurita, Kuniihiro Wasa

Theoretical Computer Science, Vol. 923, Article 44573, 2022

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

DOI: 10.1137/20M1364370
Reconstructing phylogenetic trees from multipartite quartet systems

Hiroshi Hirai, Yuni Iwamasa

Algorithmica, Vol. 84, pp. 1875-1896, 2022

DOI: 10.1007/s00453-022-00945-9
Parameterized complexity of graph burning

Yasuaki Kobayashi, Yota Otachi

Algorithmica, Vol. 84, pp. 2379-2393, 2022

DOI: 10.1007/s00453-022-00962-8
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

DOI: 10.1112/topo.12233
Linear-time recognition of double-threshold graphs

Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno

Algorithmica, Vol. 84, pp. 1163-1181, 2022

DOI: 10.1007/s00453-021-00921-9
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
Kempe equivalence classes of cubic graphs embedded on the projective plane

Kenta Ozeki

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

DOI: 10.1007/s00493-021-4330-2
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
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

DOI: 10.1007/s10107-021-01676-5
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

DOI: 10.1007/s10107-021-01625-2
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

DOI: 10.1016/j.disopt.2021.100631
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
Covering projective planar graphs with three forests

Raiji Mukae, Kenta Ozeki, Terukazu Sano, Ryuji Tazume

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

DOI: 10.1016/j.disc.2021.112748
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
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

DOI: 10.1002/jgt.22752
An O(n^2)-time algorithm for computing a max-min 3-dispersion on a point set in convex position

Yasuaki Kobayashi, Shin-Ichi Nakano, Kei Uchizawa, Takeaki Uno, Yutaro Yamaguchi, Katsuhisa Yamanaka

IEICE Transactions on Information and Systems, Vol. E105-D, pp. 503-507, 2022

DOI: 10.1587/transinf.2021FCP0013
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
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
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
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
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
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
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

Publications and Awards

DAG-pathwidth: Graph algorithmic Analyses of DAG-type blockchain networks

Path cover problems with length cost

Sorting balls and water: Equivalence and computational complexity

A spanning tree with at most $k$ leaves in a $K_{1,p}$-free graph

Note on fair game edge-connectivity of graphs

A graph minor condition for graphs to be k-linked

On reachable assignments under dichotomous preferences

Feedback vertex set reconfiguration in planar graphs

Reconfiguration of spanning trees with degree constraints or diameter constraints

Fixed-parameter algorithms for graph constraint logic

Approximability of the distance independent set problem on regular graphs and planar graphs

Reconfiguration of cliques in a graph

Graphs with large total angular resolution

Decremental optimization of vertex-coloring under the reconfiguration framework

Happy set problem on subclasses of co-comparability graphs

On robustness against evacuees' unexpected movement in automatic evacuation guiding

Special case of Rota's basis conjecture on graphic matroids

Characterization of (m,n)-linked planar graphs

A satisfiability algorithm for deterministic width-2 branching programs

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams

A 2-bisection with small number of monochromatic edges of a claw-free cubic graph

Arithmetic progressions, quasi progressions, and Gallai-Ramsey colorings

Reconfiguring (non-spanning) arborescences

Pareto efficient matchings with pairwise preferences

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

Reconfiguring k-path vertex covers

Weight balancing on boundaries

A parameterized view to the robust recoverable base problem of matroids under structural uncertainty

An improved deterministic parameterized algorithm for cactus vertex deletion

Constant amortized time enumeration of Eulerian trails

Shortest reconfiguration of perfect matchings via alternating cycles

Reconstructing phylogenetic trees from multipartite quartet systems

Parameterized complexity of graph burning

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

Linear-time recognition of double-threshold graphs

Maximum properly colored trees in edge-colored graphs

Kempe equivalence classes of cubic graphs embedded on the projective plane

Decrease and reset for power-down

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

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

Submodular reassignment problem for reallocating agents to tasks with synergy effects

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

Covering projective planar graphs with three forests

Parameterized complexity of (A, l)-path packing

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

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

An O(n^2)-time algorithm for computing a max-min 3-dispersion on a point set in convex position

Multi-pass streaming algorithms for monotone submodular function maximization

On the security number of the Cartesian product of graphs

Efficient enumeration of dominating sets for sparse graphs

Low-congestion shortcut and graph parameters

Proper colorings of plane quadrangulations without rainbow faces

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

Algorithms for gerrymandering over graphs

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

Optimal reconfiguration of optimal ladder lotteries

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