Publications and Awards
-
DAG-pathwidth: Graph algorithmic Analyses of DAG-type blockchain networks
Shoji Kasahara, Jun Kawahara, Shin-ichi Minato, Jumpei MoriIEICE Transactions on Information and Systems, Vol. E106.D, pp. 272-283, 2023 -
Path cover problems with length cost
Kenya Kobayashi, Guohui Lin, Eiji Miyano, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, Tsuyoshi YagitaAlgorithmica, Vol. 85, pp. 3348-3375, 2023 -
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 YoshinakaTheoretical Computer Science, Vol. 978, Article 114158, 2023DOI: j.tcs.2023.114158 -
A spanning tree with at most $k$ leaves in a $K_{1,p}$-free graph
Kenta Ozeki, Masao TsugakiThe Electronic Journal of Combinatorics, Vol. 30, Article 4.29, 2023DOI: 10.37236/11698 -
Note on fair game edge-connectivity of graphs
Michitaka Furuya, Naoki Matsumoto, Yumiko Ohno, Kenta OzekiDiscrete Applied Mathematics, Vol. 333, pp. 132-135, 2023 -
A graph minor condition for graphs to be k-linked
Shun-ichi MaezawaEuropean Journal of Combinatorics, Vol. 116, Article 103874, 2024 -
On reachable assignments under dichotomous preferences
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta OzekiTheoretical Computer Science, Vol. 979, Article 114196, 2023 -
Feedback vertex set reconfiguration in planar graphs
Nicolas Bousquet, Felix Hommelsheim, Yusuke Kobayashi, Moritz Mühlenthaler, Akira SuzukiTheoretical 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 WasaAlgorithmica, 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 SuzukiTheoretical Computer Science, Vol. 959, Article 113863, 2023 -
Approximability of the distance independent set problem on regular graphs and planar graphs
Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji MiyanoIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E105-A, pp. 1211-1222, 2022 -
Reconfiguration of cliques in a graph
Takehiro Ito, Hirotaka Ono, Yota OtachiDiscrete Applied Mathematics, Vol. 333, pp. 43-58, 2023 -
Graphs with large total angular resolution
Oswin Aichholzer, Matias Korman, Yoshio Okamoto, Irene Parada, Daniel Perz, André van Renssen, Birgit VogtenhuberTheoretical Computer Science, Vol. 943, pp. 73-88, 2023 -
Decremental optimization of vertex-coloring under the reconfiguration framework
Yusuke Yanagisawa, Akira Suzuki, Yuma Tamura, Xiao ZhouInternational Journal of Computer Mathematics: Computer Systems Theory, Vol. 8, pp. 80-92, 2023 -
Happy set problem on subclasses of co-comparability graphs
Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma TamuraAlgorithmica, Vol. 85, Article 44947, 2023 -
On robustness against evacuees' unexpected movement in automatic evacuation guiding
Jun Kawahara, Takanori Hara, Masahiro SasabeComputers and Electrical Engineering, Vol. 105, Article 108531, 2022 -
Special case of Rota's basis conjecture on graphic matroids
Shun-ichi Maezawa, Akiko YazawaThe Electronic Journal of Combinatorics, Vol. 29, Article P3.63, 2022DOI: 10.37236/10835 -
Characterization of (m,n)-linked planar graphs
Kengo Enami, Shun-ichi MaezawaGraphs and Combinatorics, Vol. 38, pp. 131, 2022 -
A satisfiability algorithm for deterministic width-2 branching programs
Tomu Makita, Atsuki Nagao, Tatsuki Okada, Kazuhisa Seto, Junichi TeruyamaIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, Vol. E105-A, pp. 1298-1308, 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 OzekiACM Transactions on Algorithms, Vol. 19, Article 6, 2023DOI: 10.1145/3561302 -
A 2-bisection with small number of monochromatic edges of a claw-free cubic graph
Seungjae Eom, Kenta OzekiGraphs and Combinatorics, Vol. 39, Article 44944, 2023 -
Arithmetic progressions, quasi progressions, and Gallai-Ramsey colorings
Yaping Mao, Kenta Ozeki, Aaron Robertson, Zhao WangJournal of Combinatorial Theory, Series A, Vol. 193, Article 105672, 2023 -
Reconfiguring (non-spanning) arborescences
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro WasaTheoretical Computer Science, Vol. 943, pp. 131-141, 2023 -
Pareto efficient matchings with pairwise preferences
Naoyuki KamiyamaTheoretical Computer Science, Vol. 948, Article 113707, 2023 -
An even 2-factor in the line graph of a cubic graph
SeungJae Eom, Kenta OzekiTheory and Applications of Graphs, Vol. 9, Article 7, 2022 -
Reconfiguring k-path vertex covers
Duc A. Hoang, Akira Suzuki, Tsuyoshi YagitaIEICE Transactions on Information and Systems, Vol. E105-D, pp. 1258-1272, 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 VerdonschotJournal 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 OkamotoOperations 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 OtachiTheory of Computing Systems, Vol. 66, pp. 502-515, 2022 -
Constant amortized time enumeration of Eulerian trails
Kazuhiro Kurita, Kuniihiro WasaTheoretical Computer Science, Vol. 923, Article 44573, 2022 -
Shortest reconfiguration of perfect matchings via alternating cycles
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio OkamotoSIAM Journal on Discrete Mathematics, Vol. 36, pp. 1102-1123, 2022DOI: 10.1137/20M1364370 -
Reconstructing phylogenetic trees from multipartite quartet systems
Hiroshi Hirai, Yuni IwamasaAlgorithmica, Vol. 84, pp. 1875-1896, 2022 -
Parameterized complexity of graph burning
Yasuaki Kobayashi, Yota OtachiAlgorithmica, Vol. 84, pp. 2379-2393, 2022 -
On the kernel of the surgery map restricted to the 1-loop part
Yuta Nozaki, Masatoshi Sato, Masaaki SuzukiJournal of Topology, Vol. 15, pp. 587-619, 2022DOI: 10.1112/topo.12233 -
Linear-time recognition of double-threshold graphs
Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi UnoAlgorithmica, Vol. 84, pp. 1163-1181, 2022 -
Maximum properly colored trees in edge-colored graphs
Jie Hu, Hao Li, Shun-ichi MaezawaJournal of Combinatorial Optimization, Vol. 44, pp. 154-171, 2022 -
Kempe equivalence classes of cubic graphs embedded on the projective plane
-
Decrease and reset for power-down
James Andro-Vasko, Wolfgang Bein, Hiro Ito, Shoji Kasahara, Jun KawaharaEnergy Systems, Vol. 14, pp. 445-471, 2021 -
A combinatorial algorithm for computing the rank of a generic partitioned matrix with $2 \times 2$ submatrices
Hiroshi Hirai, Yuni IwamasaMathematical 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 TakazawaMathematical Programming, Series A, Vol. 194, pp. 229-256, 2022 -
Submodular reassignment problem for reallocating agents to tasks with synergy effects
Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio OkamotoDiscrete Optimization, Vol. 44, pp. 100631, 2022 -
The Alon-Tarsi number of K5-minor-free graphs
Toshiki Abe, Seog-Jin Kim, Kenta OzekiDiscrete Mathematics, Vol. 345, pp. 112764, 2022 -
Covering projective planar graphs with three forests
Raiji Mukae, Kenta Ozeki, Terukazu Sano, Ryuji TazumeDiscrete 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 OtachiAlgorithmica, 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 YoshidaSIAM Journal on Discrete Mathematics, Vol. 36, pp. 355-382, 2022DOI: 10.1137/20M1357317 -
A forbidden pair for connected graphs to have spanning k-trees
Shun-ichi Maezawa, Kenta OzekiJournal of Graph Theory, Vol. 99, pp. 509-519, 2022DOI: 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 YamanakaIEICE Transactions on Information and Systems, Vol. E105-D, pp. 503-507, 2022 -
Multi-pass streaming algorithms for monotone submodular function maximization
Chien-Chung Huang, Naonori KakimuraTheory of Computing Systems, Vol. 66, pp. 354-394, 2022 -
On the security number of the Cartesian product of graphs
Marko Jakovac, Yota OtachiDiscrete Applied Mathematics, Vol. 304, pp. 119-128, 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 -
Proper colorings of plane quadrangulations without rainbow faces
Kengo Enami, Kenta Ozeki, Tomoki YamaguchiGraphs and Combinatorics, Vol. 37, pp. 1873-1890, 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 -
Algorithms for gerrymandering over graphs
Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio OkamotoTheoretical Computer Science, Vol. 868, pp. 30-45, 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 -
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