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

  DOI: 10.1007/978-3-031-22105-7_26

• 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

• 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

  DOI: 10.4230/LIPIcs.ISAAC.2022.20

• 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

  DOI: 10.1007/978-3-031-21203-1_43

• 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

• 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

  DOI: 10.4230/LIPIcs.ISAAC.2022.4

• 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

• 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

  DOI: 10.4230/LIPIcs.FUN.2022.16

• 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

• 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

  DOI: 10.4230/LIPIcs.MFCS.2022.6

• 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

  DOI: 10.4230/LIPIcs.ESA.2022.61

• 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

  DOI: 10.1007/978-3-031-15914-5_25

• 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

  DOI: 10.1145/3517804.3524148

• 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

• 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

  DOI: 10.4230/LIPIcs.MFCS.2022.58

• 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

• 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

  DOI: 10.4204/EPTCS.372.21

• Parameterized complexity of graph burning

  Yasuaki Kobayashi, Yota Otachi

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

  DOI: 10.1007/s00453-022-00962-8

• 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

  DOI: 10.4230/LIPIcs.SoCG.2022.12

• 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

• 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

  DOI: 10.1137/1.9781611977073.56

• 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

• 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

  DOI: 10.1609/aaai.v36i5.20441

• 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

  DOI: 10.1609/aaai.v36i4.20290

• 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

• 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

• 情報処理学会 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

  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

• 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

  DOI: 10.1007/978-3-030-96731-4_4

• 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

  DOI: 10.1007/978-3-030-96731-4_32

• 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

  DOI: 10.1007/978-3-030-96731-4_13

• 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

  DOI: 10.4230/LIPIcs.STACS.2022.15

• 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

• 日本応用数理学会 第18回若手優秀講演賞

  岩政 勇仁 (京都大学)
  「2×2型分割多項式行列の行列式次数を求める組合せ的多項式時間アルゴリズム」

  2022年6月17日受賞

• 第20回LA/EATCS-Japan発表論文賞

  川原 純 (京都大学)

  「ZDDを用いた組合せ遷移ソルバーについての考察」

  著者：伊藤 健洋 (東北大学)，川原 純 (京都大学)，宋 剛秀 (神戸大学)，鈴木 顕 (東北大学)，照山 順一 (兵庫県立大学)，戸田 貴久 (電気通信大学)

  2022年2月3日受賞