活動情報

論文・受賞

2022

  • Reallocation problems with minimum completion time

    Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka Ono
    Proc. of 28th International Computing and Combinatorics Conference (COCOON 2022), Lecture Notes in Computer Science, Vol. 13595, pp. 292-304, 2022
  • 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
  • Extended MSO model checking via small vertex integrity

    Tatsuya Gima, Yota Otachi
    Proc. of 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz International Proceedings in Informatics, Vol. 248, pp. 20:1-20:15, 2022
  • On reachable assignments under dichotomous preferences

    Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
    Proc. of 24th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA 2022), Lecture Notes in Computer Science, Vol. 13753, pp. 650-658, 2022
  • 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
  • Algorithms for coloring reconfiguration under recolorability digraphs

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Akira Suzuki
    Proc. of 33rd International Symposium on Algorithms and Computation (ISAAC 2022), Leibniz International Proceedings in Informatics, Vol. 248, pp. 4:1–4:19, 2022
  • 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
  • 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
    Proc. of 11th International Conference on Fun with Algorithms (FUN 2022), Leibniz International Proceedings in Informatics, Vol. 226, pp. 16:1-16:17, 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
  • Parameterized complexity of non-separating and non-disconnecting paths and sets

    Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi, Saket Saurabh
    Proc. of 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022), Leibniz International Proceedings in Informatics, Vol. 241, pp. 6:1-6:15, 2022
  • Algorithmic meta-theorems for combinatorial reconfiguration revisited

    Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi
    Proc. of 30th Annual European Symposium on Algorithms (ESA 2022), Leibniz International Proceedings in Informatics, Vol. 244, pp. 61:1-61:15, 2022
  • Polynomial-delay and polynomial-space enumeration of large maximal matchings

    Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
    Proc. of 48th edition of the International Workshop on Graph-Theoretic Concepts in Computer Science (WG2022), Vol. 13453, pp. 342-355, 2022
  • Linear-delay enumeration for minimal Steiner problems

    Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa
    Proc. of 41st ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2022), pp. 301-313, 2022
  • Constant amortized time enumeration of Eulerian trails

    Kazuhiro Kurita, Kuniihiro Wasa
    Theoretical Computer Science, Vol. 923, Article 44573, 2022
  • Independent set reconfiguration on directed graphs

    Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, Kunihiro Wasa
    Proc. of 47th International Symposium on Mathematical Foundations of Computer Science, Leibniz International Proceedings in Informatics, Vol. 241, pp. 58:1-58:15, 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
  • Quantaloidal approach to constraint satisfaction

    Soichiro Fujii, Yuni Iwamasa, Kei Kimura
    Proc. of 4th International Conference on Applied Category Theory (ACT 2021), Electronic Proceedings in Theoretical Computer Science, Vol. 372, pp. 289-305, 2022
  • Parameterized complexity of graph burning

    Yasuaki Kobayashi, Yota Otachi
    Algorithmica, Vol. 84, pp. 2379-2393, 2022
  • Unlabeled multi-robot motion planning with tighter separation bounds

    Bahareh Banyassady, Mark de Berg, Karl Bringmann, Kevin Buchin, Henning Fernau, Dan Halperin, Irina Kostitsyna, Yoshio Okamoto, Stijn Slot
    Proc. of 38th International Symposium on Computational Geometry (SoCG 2022), Leibniz International Proceedings in Informatics, Vol. 224, pp. 12:1-12:16, 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
  • 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
    Proc. of Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pp. 1342-1355, 2022
  • Linear-time recognition of double-threshold graphs

    Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno
    Algorithmica, Vol. 84, pp. 1163-1181, 2022
  • Reforming an envy-free matching

    Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki
    Proc. of 36th AAAI Conference on Artificial Intelligence (AAAI 2022), Vol. 36, pp. 5084-5091, 2022
  • Computing diverse shortest paths efficiently: A theoretical and experimental study

    Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, Yota Otachi
    Proc. of 36th AAAI Conference on Artificial Intelligence (AAAI 2022), Vol. 36, pp. 3758-3766, 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
  • 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
  • 情報処理学会 2022年度山下記念研究賞

    和佐 州洋 (法政大学)
    「Constant Amortized Time Enumeration of Eulerian trails (2021-AL-183)」
    2023年3月2日受賞
  • 日本オペレーションズ・リサーチ学会 第12回研究賞奨励賞

    岩政 勇仁 (京都大学)
    2022年9月14日受賞
  • 国際プログラミング競技会 XCSP3 Competition 2022 Main CSP部門 第2位

    宋 剛秀 (神戸大学),Daniel Le Berre (CRIL-CNRS),鍋島 英知 (山梨大学),番原 睦則 (名古屋大学),田村 直之 (神戸大学)
    2022年8月3日受賞
  • 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
  • Reconfiguration of regular induced subgraphs

    Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, Kunihiro Wasa
    Proc. of 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), Lecture Notes in Computer Science, Vol. 13174, pp. 35-46, 2022
  • Path cover problems with length cost

    Kenya Kobayashi, Guohui Lin, Eiji Miyano, Toshiki Saitoh, Akira Suzuki, Tadatoshi Utashima, Tsuyoshi Yagita
    Proc. of 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), Lecture Notes in Computer Science, Vol. 13174, pp. 396-408, 2022
  • Happy set problem on subclasses of co-comparability graphs

    Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura
    Proc. of 16th International Conference and Workshops on Algorithms and Computation (WALCOM 2022), Lecture Notes in Computer Science, Vol. 13174, pp. 149-160, 2022
  • Reconfiguration of spanning trees with degree constraint or diameter constraint

    Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, Kunihiro Wasa
    Proc. of 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), Leibniz International Proceedings in Informatics, Vol. 219, pp. 15:1-15:21, 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
  • 日本応用数理学会 第18回若手優秀講演賞

    岩政 勇仁 (京都大学)
    「2×2型分割多項式行列の行列式次数を求める組合せ的多項式時間アルゴリズム」
    2022年6月17日受賞
  • 第20回LA/EATCS-Japan発表論文賞

    川原 純 (京都大学)
    「ZDDを用いた組合せ遷移ソルバーについての考察」
    著者:伊藤 健洋 (東北大学),川原 純 (京都大学),宋 剛秀 (神戸大学),鈴木 顕 (東北大学),照山 順一 (兵庫県立大学),戸田 貴久 (電気通信大学)
    2022年2月3日受賞