Publications and Awards
-
Reallocation problems with minimum completion time
Toshimasa Ishii, Jun Kawahara, Kazuhisa Makino, Hirotaka OnoProc. 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 MiyanoIEICE 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 OtachiProc. 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 OzekiProc. 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 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 -
Algorithms for coloring reconfiguration under recolorability digraphs
Soichiro Fujii, Yuni Iwamasa, Kei Kimura, Akira SuzukiProc. 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 OzekiTheory 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 YoshinakaProc. 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 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 -
Parameterized complexity of non-separating and non-disconnecting paths and sets
Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi, Saket SaurabhProc. 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 OtachiProc. 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 WasaProc. 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 WasaProc. 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 WasaTheoretical 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 WasaProc. 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 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 -
Quantaloidal approach to constraint satisfaction
Soichiro Fujii, Yuni Iwamasa, Kei KimuraProc. of 4th International Conference on Applied Category Theory (ACT 2021), Electronic Proceedings in Theoretical Computer Science, Vol. 372, pp. 289-305, 2022DOI: 10.4204/EPTCS.372.21 -
Parameterized complexity of graph burning
Yasuaki Kobayashi, Yota OtachiAlgorithmica, 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 SlotProc. 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 SuzukiJournal of Topology, Vol. 15, pp. 587-619, 2022DOI: 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 OzekiProc. 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 UnoAlgorithmica, 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 OzekiProc. 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 OtachiProc. 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 MaezawaJournal of Combinatorial Optimization, Vol. 44, pp. 154-171, 2022 -
Kempe equivalence classes of cubic graphs embedded on the projective plane
-
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 -
12th Research Encourage Award, the Operations Research Society of Japan
IWAMASA, Yuni (Kyoto U.)
Sepetember 14, 2022 -
XCSP3 Competition 2022, 2nd place of the Main CSP track
SOH, Takehide (Kobe U.), LE BERRE, Daniel (CRIL-CNRS), NABESHIMA, Hidetomo (Yamanashi U.), BANBARA, Mutsunori (Nagoya U.), TAMURA, Naoyuki (Kobe U.)
August 3, 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 -
Reconfiguration of regular induced subgraphs
Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, Kunihiro WasaProc. 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 YagitaProc. 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 TamuraProc. 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 WasaProc. 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 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 -
18th Young Scientists' Presentation Award, the Japan Society for Industrial and Applied Mathematics
IWAMASA, Yuni (Kyoto U.)”A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with 2×2 submatrices”June 17, 2022 -
20th LA/EATCS-Japan Presentation Award
KAWAHARA, Jun (Kyoto U.)"On an efficient solver for combinatorial reconfiguration problems using ZDDs"Authors: ITO, Takehiro (Tohoku U.), KAWAHARA, Jun (Kyoto U.), SOH, Takehide (Kobe U.), SUZUKI, Akira (Tohoku U.), TERUYAMA, Junichi (U. Hyogo), TODA, Takahisa (U. Electro-Communications)February 3, 2022