論文・受賞
C01
-
情報処理学会 2023年度コンピュータサイエンス領域功績賞
岡本 吉央 (電気通信大学)2024年1月21日受賞 -
Reconfiguration of colorings in triangulations of the sphere
Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta OzekiProc. of 39th International Symposium on Computational Geometry (SoCG 2023), Leibniz International Proceedings in Informatics, Vol. 258, pp. 43:1-43:16, 2023 -
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 -
Reconfiguration of the union of arborescences
Yusuke Kobayashi, Ryoga Mahara, Tamás SchwarczProc. of 34th International Symposium on Algorithms and Computation (ISAAC 2023), Leibniz International Proceedings in Informatics, Vol. 283, pp. 48:1-48:14, 2023 -
Algorithmic theory of qubit routing
Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio OkamotoProc. of 18th Algorithms and Data Structures Symposium (WADS 2023), Lecture Notes in Computer Science, Vol. 14079, pp. 533–546, 2023 -
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 -
Reconfiguration and enumeration of optimal cyclic ladder lotteries
Yuta Nozaki, Katsuhisa Yamanaka, Kunihiro WasaProc. of 34th International Workshop on Combinatorial Algorithms (IWOCA 2023), Lecture Notes in Computer Science, Vol. 13889, pp. 331-342, 2023 -
Rerouting planar curves and disjoint paths
Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta OzekiProc. of 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023), Leibniz International Proceedings in Informatics, Vol. 261, pp. 81:1-81:19, 2023 -
Reconfiguration of time-respecting arborescences
Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira SuzukiProc. of 18th Algorithms and Data Structures Symposium (WADS 2023), Lecture Notes in Computer Science, Vol. 14079, pp. 521-532, 2023 -
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 -
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 -
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 -
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 -
A framework to design approximation algorithms for finding diverse solutions in combinatorial problems
Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota OtachiProc. of 37th AAAI Conference on Artificial Intelligence (AAAI 2023), AAAI-23 Technical Tracks 4, Vol. 37, pp. 3968-3976, 2023 -
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 -
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 -
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 -
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 -
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 -
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 -
Online task assignment problems with reusable resources
Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, Ken-ichi KawarabayashiProc. of 36th AAAI Conference on Artificial Intelligence (AAAI 2022), Vol. 36, pp. 5199-5207, 2021 -
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 -
日本オペレーションズ・リサーチ学会 第13回研究賞
小林 佑輔 (京都大学)2023年9月14日受賞 -
日本オペレーションズ・リサーチ学会 第12回研究賞奨励賞
岩政 勇仁 (京都大学)2022年9月14日受賞 -
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 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 -
Multi-pass streaming algorithms for monotone submodular function maximization
Chien-Chung Huang, Naonori KakimuraTheory of Computing Systems, Vol. 66, pp. 354-394, 2022 -
Distributed reconfiguration of spanning trees
Yukiko Yamauchi, Naoyuki Kamiyama, Yota OtachiProc. of 23rd International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2021), Lecture Notes in Computer Science, Vol. 13046, pp. 516-520, 2021 -
Reconfiguring directed trees in a digraph
Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro WasaProc. of 27th International Computing and Combinatorics Conference (COCOON 2021), Lecture Notes in Computer Science, Vol. 13025, pp. 343-354, 2021 -
Proper colorings of plane quadrangulations without rainbow faces
Kengo Enami, Kenta Ozeki, Tomoki YamaguchiGraphs and Combinatorics, Vol. 37, pp. 1873-1890, 2021 -
日本応用数理学会 第18回若手優秀講演賞
岩政 勇仁 (京都大学)
「2×2型分割多項式行列の行列式次数を求める組合せ的多項式時間アルゴリズム」2022年6月17日受賞 -
Dynamic bipartite matching market with arrivals and departures
Naonori Kakimura, Donghao ZhuProc. of 17th Conference on Web and Internet Economics (WINE 2021), Lecture Notes in Computer Science, Vol. 13112, pp. 544, 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 -
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 -
Algorithms for gerrymandering over graphs
Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio OkamotoTheoretical Computer Science, Vol. 868, pp. 30-45, 2021 -
A combinatorial algorithm for computing the degree of the determinant of a generic partitioned polynomial matrix with $2 \time 2$ submatrices
Yuni IwamasaProc. of 22nd Conference on Integer Programming and Combinatorial Optimization (IPCO 2021), Lecture Notes in Computer Science, Vol. 12707, pp. 119-133, 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 -
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 -
FIT2020 船井ベストペーパー賞
岡本 吉央 (電気通信大学),伊藤 健洋 (東北大学),垣村 尚徳 (慶應義塾大学),神山 直之 (九州大学),小林 佑輔 (京都大学)「構造変化に応じるロバスト修復可能マトロイド基問題に対する固定パラメータアルゴリズム」
2021年8月26日受賞 -
第9回藤原洋数理科学賞奨励賞
小林 佑輔 (京都大学)「離散最適化問題に対する効率的アルゴリズムの研究」2020年10月17日受賞