活動情報

論文・受賞

学術雑誌

  • 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
    • 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
      • 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
        • 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
          • 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
            • A graph minor condition for graphs to be k-linked

              Shun-ichi Maezawa
              European 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 Ozeki
                Theoretical Computer Science, Vol. 979, Article 114196, 2023
                • 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
                  • 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
                    • 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
                      • 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
                        • Reconfiguration of cliques in a graph

                          Takehiro Ito, Hirotaka Ono, Yota Otachi
                          Discrete 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 Vogtenhuber
                            Theoretical Computer Science, Vol. 943, pp. 73-88, 2023
                            • 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
                              • 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
                                • 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
                                  • 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
                                    • Characterization of (m,n)-linked planar graphs

                                      Kengo Enami, Shun-ichi Maezawa
                                      Graphs 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 Teruyama
                                        IEICE 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 Ozeki
                                          ACM Transactions on Algorithms, Vol. 19, Article 6, 2023
                                          • 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
                                            • 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
                                              • 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
                                                • Pareto efficient matchings with pairwise preferences

                                                  Naoyuki Kamiyama
                                                  Theoretical Computer Science, Vol. 948, Article 113707, 2023
                                                  • 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
                                                    • 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
                                                      • 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
                                                        • 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
                                                          • 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
                                                            • Constant amortized time enumeration of Eulerian trails

                                                              Kazuhiro Kurita, Kuniihiro Wasa
                                                              Theoretical Computer Science, Vol. 923, Article 44573, 2022
                                                              • 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
                                                                • Reconstructing phylogenetic trees from multipartite quartet systems

                                                                  Hiroshi Hirai, Yuni Iwamasa
                                                                  Algorithmica, Vol. 84, pp. 1875-1896, 2022
                                                                  • Parameterized complexity of graph burning

                                                                    Yasuaki Kobayashi, Yota Otachi
                                                                    Algorithmica, Vol. 84, pp. 2379-2393, 2022
                                                                    • 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
                                                                      • Linear-time recognition of double-threshold graphs

                                                                        Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno
                                                                        Algorithmica, Vol. 84, pp. 1163-1181, 2022
                                                                        • 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
                                                                          • Kempe equivalence classes of cubic graphs embedded on the projective plane

                                                                            Kenta Ozeki
                                                                            Combinatorica, Vol. 42, pp. 1451-1480, 2022
                                                                            • 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
                                                                              • 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
                                                                                • 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
                                                                                  • 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
                                                                                    • The Alon-Tarsi number of K5-minor-free graphs

                                                                                      Toshiki Abe, Seog-Jin Kim, Kenta Ozeki
                                                                                      Discrete Mathematics, Vol. 345, pp. 112764, 2022
                                                                                      • Covering projective planar graphs with three forests

                                                                                        Raiji Mukae, Kenta Ozeki, Terukazu Sano, Ryuji Tazume
                                                                                        Discrete 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 Otachi
                                                                                          Algorithmica, 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 Yoshida
                                                                                            SIAM Journal on Discrete Mathematics, Vol. 36, pp. 355-382, 2022
                                                                                            • 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
                                                                                              • 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
                                                                                                • Multi-pass streaming algorithms for monotone submodular function maximization

                                                                                                  Chien-Chung Huang, Naonori Kakimura
                                                                                                  Theory of Computing Systems, Vol. 66, pp. 354-394, 2022
                                                                                                  • On the security number of the Cartesian product of graphs

                                                                                                    Marko Jakovac, Yota Otachi
                                                                                                    Discrete Applied Mathematics, Vol. 304, pp. 119-128, 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
                                                                                                        • Proper colorings of plane quadrangulations without rainbow faces

                                                                                                          Kengo Enami, Kenta Ozeki, Tomoki Yamaguchi
                                                                                                          Graphs 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 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
                                                                                                                              • Algorithms for gerrymandering over graphs

                                                                                                                                Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto
                                                                                                                                Theoretical 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 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
                                                                                                                                    • 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