Publications of Yusuke Kobayashi

Journal Articles

  1. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki: On reachable assignments under dichotomous preferences, Theoretical Computer Science, 979 (2023), 114196.
  2. Nicolas Bousquet, Felix Hommelsheim, Yusuke Kobayashi, Moritz Mühlenthaler, and Akira Suzuki: Feedback vertex set reconfiguration in planar graphs, Theoretical Computer Science, 979 (2023), 114188.
  3. Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, and Akira Suzuki: Fixed-parameter algorithms for graph constraint logic, Theoretical Computer Science, 959 (2023), 113863.
  4. Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa: Reconfiguration of spanning trees with degree constraints or diameter constraints, Algorithmica, 85 (2023), pp. 2779--2816.
  5. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki: Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams, ACM Transactions on Algorithms, 19 (2023), Article 6.
  6. Yusuke Kobayashi and Ryoga Mahara: Approximation algorithm for Steiner tree problem with neighbor-induced cost, Journal of the Operations Research Society of Japan, 66 (2023), pp. 18--36.
  7. Toshimasa Ishii, Akitoshi Kawamura, Yusuke Kobayashi, and Kazuhisa Makino: Trade-offs among degree, diameter, and number of paths, Discrete Applied Mathematics, 327 (2023), pp. 96--100.
  8. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto: A parameterized view to the robust recoverable base problem of matroids under structural uncertainty, Operations Research Letters, 50 (2022), pp. 370--375.
  9. Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Submodular reassignment problem for reallocating agents to tasks with synergy effects, Discrete Optimization, 44 (2022), 100631.
  10. Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, and Yota Otachi: An improved deterministic parameterized algorithm for cactus vertex deletion, Theory of Computing Systems, 66 (2022), pp. 502--515.
  11. Satoru Iwata and Yusuke Kobayashi: A weighted linear matroid parity algorithm, SIAM Journal on Computing, 51 (2022), pp. STOC17-238--STOC17-280.
  12. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Shortest reconfiguration of perfect matchings via alternating cycles, SIAM Journal on Discrete Mathematics, 36 (2022), pp. 1102--1123.
  13. Yusuke Kobayashi: Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles, Mathematical Programming, Series B, 192 (2022), pp. 675--702.
  14. Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Yushi Uno, Linear-time recognition of double-threshold graphs, Algorithmica, 84 (2022), pp. 1163--1181.
  15. Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, and Yota Otachi: Parameterized complexity of (A, l)-path packing, Algorithmica, 84 (2022), pp. 871--895.
  16. Kristóf Bérczi, Naonori Kakimura, and Yusuke Kobayashi: Market pricing for matroid rank valuations, SIAM Journal on Discrete Mathematics, 35 (2021), pp. 2662--2678.
  17. Yuval Filmus, Yasushi Kawase, Yusuke Kobayashi, and Yutaro Yamaguchi: Tight approximation for unconstrained XOS maximization, Mathematics of Operations Research, 46 (2021), pp. 1599--1610.
  18. Yoichi Iwata and Yusuke Kobayashi: Improved analysis of highest-degree branching for feedback vertex set, Algorithmica, 83 (2021), pp. 2503--2520.
  19. Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Algorithms for gerrymandering over graphs, Theoretical Computer Science, 868 (2021), pp. 30--45.
  20. Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, and Tsuyoshi Yagita: Finding a maximum minimal separator: graph classes and fixed-parameter tractability, Theoretical Computer Science, 865 (2021), pp. 131--140.
  21. 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: Computing the largest bond and the maximum connected cut of a graph, Algorithmica, 83 (2021), pp. 1421--1458.
  22. Takehiro Ito, Naonori Kakimura, and Yusuke Kobayashi: Complexity of the multi-service center problem, Theoretical Computer Science, 842 (2020), pp. 18--27.
  23. Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, and Kunihiro Wasa: Diameter of colorings under Kempe changes, Theoretical Computer Science, 838 (2020), pp. 45--57.
  24. Koki Takayama and Yusuke Kobayashi: On the number of edges in a graph with many two-hop disjoint paths, Discrete Applied Mathematics, 283 (2020), pp. 718--723.
  25. Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Tom C. van der Zanden: Subgraph isomorphism on graph classes that exclude a substructure, Algorithmica, 82 (2020), pp. 3566--3587.
  26. Yasushi Kawase, Yusuke Kobayashi, and Yutaro Yamaguchi: Finding a path with two labels forbidden in group-labeled graphs, Journal of Combinatorial Theory, Series B, 143 (2020), pp. 65--122.
  27. Ken-ichi Kawarabayashi and Yusuke Kobayashi: Linear min-max relation between the treewidth of an H-minor-free graph and its largest grid minor, Journal of Combinatorial Theory, Series B, 141 (2020), pp. 165--180.
  28. Koki Takayama and Yusuke Kobayashi: A strongly polynomial time algorithm for the maximum supply rate problem on trees, Theoretical Computer Science, 806 (2020), pp. 323--331.
  29. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Reconfiguration of maximum-weight b-matchings in a graph, Journal of Combinatorial Optimization, 37 (2019), pp. 454--464.
  30. Yusuke Kobayashi and Ryo Sako: Two disjoint shortest paths problem with non-negative edge length, Operations Research Letters, 47 (2019), pp. 66--69.
  31. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Minimum-cost b-edge dominating sets on trees, Algorithmica, 81 (2019), pp. 343--366.
  32. Yusuke Kobayashi: NP-hardness and fixed-parameter tractability of the minimum spanner problem, Theoretical Computer Science, 746 (2018), pp. 88--97.
  33. Ken-ichi Kawarabayashi and Yusuke Kobayashi: All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs, SIAM Journal on Computing, 47 (2018), pp. 1483--1504.
  34. Than Nguyen Hau, Naonori Kakimura, Ken-ichi Kawarabayashi, Yusuke Kobayashi, Tatsuya Matsuoka, and Yu Yokoi: Optimal cache placement for an academic backbone network, Journal of the Operations Research Society of Japan, 61 (2018), pp. 197--216.
  35. Hiroshi Nishiyama, Yusuke Kobayashi, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita: The parity Hamiltonian cycle problem, Discrete Mathematics, 341 (2018), pp. 606--626.
  36. Yusuke Kobayashi and Kenjiro Takazawa: Randomized strategies for cardinality robustness in the knapsack problem, Theoretical Computer Science, 699 (2017), pp. 53--62.
  37. Kristóf Bérczi and Yusuke Kobayashi: An algorithm for identifying cycle-plus-triangles graphs, Discrete Applied Mathematics, 226 (2017), pp. 10--16.
  38. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Efficient stabilization of cooperative matching games, Theoretical Computer Science, 677 (2017), pp. 69--82.
  39. Naonori Kakimura, Ken-ichi Kawarabayashi, and Yusuke Kobayashi: Packing edge-disjoint odd Eulerian subgraphs through prescribed vertices in 4-edge-connected graphs, SIAM Journal on Discrete Mathematics, 31 (2017), pp. 766--782.
  40. Yusuke Kobayashi and Sho Toyooka: Finding a shortest non-zero path in group-labeled graphs via permanent computation, Algorithmica, 77 (2017), pp. 1128--1142.
  41. Ken-ichi Kawarabayashi and Yusuke Kobayashi: An improved approximation algorithm for the edge-disjoint paths problem with congestion two, ACM Transactions on Algorithms, 13 (2016), Article 5.
  42. Kristóf Bérczi, Tamás Király, and Yusuke Kobayashi: Covering intersecting bi-set families under matroid constraints, SIAM Journal on Discrete Mathematics, 30 (2016), pp. 1758--1774.
  43. Ken-ichi Kawarabayashi and Yusuke Kobayashi: Edge-disjoint odd cycles in 4-edge-connected graphs, Journal of Combinatorial Theory, Series B, 119 (2016), pp. 12--27.
  44. Kensuke Otsuki, Yusuke Kobayashi, and Kazuo Murota: Improved max-flow min-cut algorithms in a circular disk failure model with application to a road network, European Journal of Operational Research, 248 (2016), pp. 396--403.
  45. Attila Bernáth, Yusuke Kobayashi, and Tatsuya Matsuoka: The generalized terminal backup problem, SIAM Journal on Discrete Mathematics, 29 (2015), pp. 1764--1782.
  46. Kota Ishihara and Yusuke Kobayashi: Routing algorithms under mutual interference constraints, Journal of the Operations Research Society of Japan, 58 (2015), pp. 209--222.
  47. Yusuke Kobayashi: The complexity of minimizing the difference of two M♮-convex set functions, Operations Research Letters, 43 (2015), pp. 573--574.
  48. Ken-ichi Kawarabayashi and Yusuke Kobayashi: The edge-disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, Combinatorica, 35 (2015), pp. 477--495.
  49. Holger Flier, Yusuke Kobayashi, Matúš Mihalák, Anita Schöbel, Peter Widmayer, and Anna Zych: Selecting vertex disjoint paths in plane graphs, Networks, 66 (2015), pp. 136--144.
  50. Akitoshi Kawamura and Yusuke Kobayashi: Fence patrolling by mobile agents with distinct speeds, Distributed Computing, 28 (2015), pp. 147--154.
  51. Yusuke Kobayashi: Triangle-free 2-matchings and M-concave functions on jump systems, Discrete Applied Mathematics, 175 (2014), pp. 35--42.
  52. Ryo Fujita, Yusuke Kobayashi, and Kazuhisa Makino: Robust matchings and matroid intersections, SIAM Journal on Discrete Mathematics, 27 (2013), pp. 1234--1256.
  53. Ken-ichi Kawarabayashi and Yusuke Kobayashi: An O(log n)-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs, ACM Transactions on Algorithms, 9 (2013), Article 16.
  54. Yusuke Kobayashi, Kazuo Murota, and Robert Weismantel: Cone superadditivity of discrete convex functions, Mathematical Programming, Series A, 135 (2012), pp. 25--44.
  55. Ken-ichi Kawarabayashi and Yusuke Kobayashi: Fixed-parameter tractability for the subset feedback set problem and the S-cycle packing problem, Journal of Combinatorial Theory, Series B, 102 (2012), pp. 1020--1034.
  56. Yusuke Kobayashi, Jácint Szabó, and Kenjiro Takazawa: A proof of Cunningham's conjecture on restricted subgraphs and jump systems, Journal of Combinatorial Theory, Series B, 102 (2012), pp. 948--966.
  57. Yusuke Kobayashi and Yuichi Yoshida: Algorithms for finding a maximum non-k-linked graph, SIAM Journal on Discrete Mathematics, 26 (2012), pp. 591--604.
  58. Yusuke Kobayashi and Xin Yin: An algorithm for finding a maximum t-matching excluding complete partite subgraphs, Discrete Optimization, 9 (2012), pp. 98--108.
  59. Yuichi Yoshida and Yusuke Kobayashi: Testing the (s,t)-disconnectivity of graphs and digraphs, Theoretical Computer Science, 434 (2012), pp. 98--113.
  60. Ken-ichi Kawarabayashi and Yusuke Kobayashi: An immersion of a square in 4-edge-connected graphs, Progress in Informatics, 9 (2012), pp. 35--36.
  61. Ken-ichi Kawarabayashi and Yusuke Kobayashi: A linear time algorithm for the induced disjoint paths problem in planar graphs, Journal of Computer and System Sciences, 78 (2012), pp. 670--680.
  62. Kristóf Bérczi and Yusuke Kobayashi: An algorithm for (n-3)-connectivity augmentation problem: jump system approach, Journal of Combinatorial Theory, Series B, 102 (2012), pp. 565--587.
  63. Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Bruce Reed: The disjoint paths problem in quadratic time, Journal of Combinatorial Theory, Series B, 102 (2012), pp. 424--435.
  64. Shinji Imahori, Yuichiro Miyamoto, Hideki Hashimoto, Yusuke Kobayashi, Mihiro Sasaki, and Mutsunori Yagiura: The complexity of the node capacitated in-tree packing problem, Networks, 59 (2012), pp. 13--21.
  65. Ken-ichi Kawarabayashi and Yusuke Kobayashi: An improved algorithm for the half-disjoint paths problem, SIAM Journal on Discrete Mathematics, 25 (2011), pp. 1322--1330.
  66. Ken-ichi Kawarabayashi and Yusuke Kobayashi: Algorithms for finding an induced cycle in planar graphs, Combinatorica, 30 (2010), pp. 715--734.
  67. Yusuke Kobayashi and Christian Sommer: On shortest disjoint paths in planar graphs, Discrete Optimization, 7 (2010), pp. 234--245.
  68. Yusuke Kobayashi: A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs, Discrete Optimization, 7 (2010), pp. 197--202.
  69. Satoru Iwata and Yusuke Kobayashi: An algorithm for minimum cost arc-connectivity orientations, Algorithmica, 56 (2010), pp. 437--447.
  70. Yusuke Kobayashi: Induced disjoint paths problem in a planar digraph, Discrete Applied Mathematics, 157 (2009), pp. 3231--3238.
  71. Yusuke Kobayashi and Kenjiro Takazawa: Even factors, jump systems, and discrete convexity, Journal of Combinatorial Theory, Series B, 99 (2009), pp. 139--161.
  72. Yusuke Kobayashi and Kazuo Murota: Induction of M-convex functions by linking systems, Discrete Applied Mathematics, 155 (2007), pp. 1471--1480.
  73. Yusuke Kobayashi, Kazuo Murota, and Ken'ichiro Tanaka: Operations on M-convex functions on jump systems, SIAM Journal on Discrete Mathematics, 21 (2007), pp. 107--129.

Refereed Conference Proceedings

  1. Yusuke Kobayashi, Ryoga Mahara, and Tamás Schwarcz: Reconfiguration of the union of arborescences, Proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023), 44:1--44:14, 2023.
  2. Yusuke Kobayashi and Takashi Noguchi: An approximation algorithm for two-edge-connected subgraph problem via triangle-free two-edge-cover, Proceedings of the 34th International Symposium on Algorithms and Computation (ISAAC 2023), 43:1--43:10, 2023.
  3. Yusuke Kobayashi, Ryoga Mahara, and Souta Sakamoto: EFX allocations for indivisible chores: matching-based approach, Proceedings of the 16th International Symposium on Algorithmic Game Theory (SAGT 2023), pp. 257--270.
  4. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Algorithmic theory of qubit routing, Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023), pp. 533--546.
  5. Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, and Akira Suzuki: Reconfiguration of time-respecting arborescences, Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023), pp. 521--532.
  6. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, and Yoshio Okamoto: Hardness of finding combinatorial shortest paths on graph associahedra, Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023), 82:1--82:17, 2023.
  7. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki: Rerouting planar curves and disjoint paths, Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023), 81:1--81:19, 2023.
  8. Yusuke Kobayashi: Optimal general factor problem and jump system intersection, Proceedings of the 24th Conference on Integer Programming and Combinatorial Optimization (IPCO 2023), pp. 291--305, 2023.
  9. Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki: Reconfiguration of colorings in triangulations of the sphere, Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023), 43:1--43:16.
  10. Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, and Yota Otachi: A framework to design approximation algorithms for finding diverse solutions in combinatorial problems, Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023), pp. 3968--3976.
  11. Yusuke Kobayashi and Ryoga Mahara: Proportional allocation of indivisible goods up to the least valued good on average, Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), 55:1--55:13.
  12. Yusuke Kobayashi and Tatsuya Terao: One-face shortest disjoint paths with a deviation terminal, Proceedings of the 33rd International Symposium on Algorithms and Computation (ISAAC 2022), 47:1--47:15.
  13. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki: On reachable assignments under dichotomous preferences, Proceedings of the 24th International Conference on Principles and Practice of Multi-Agent Systems (PRIMA 2022), pp. 650--658.
  14. Asei Inoue and Yusuke Kobayashi: An additive approximation scheme for the Nash social welfare maximization with identical additive valuations, Proceedings of the 33rd International Workshop on Combinatorial Algorithms (IWOCA 2022), pp. 341--354.
  15. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki: Reforming an envy-free matching, Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI 2022), pp. 5084--5091.
  16. Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa: Reconfiguration of spanning trees with degree constraint or diameter constraint, Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022), 15:1--15:21.
  17. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki: Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams, Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA 2022), pp. 1342--1355.
  18. Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, and Akira Suzuki: Fixed-parameter algorithms for graph constraint logic, Proceedings of the 15th International Symposium on Parameterized and Exact Computation (IPEC 2020), 15:1--15:15.
  19. Kristóf Bérczi, Naonori Kakimura, and Yusuke Kobayashi: Market pricing for matroid rank valuations, Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC 2020), 39:1--39:15.
  20. Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa: Reconfiguration of spanning trees with many or few leaves, Proceedings of the 28th European Symposium on Algorithms (ESA 2020), 24:1--24:15.
  21. Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Yushi Uno, Linear-time recognition of double-threshold graphs, Proceedings of the 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020), pp. 286--297.
  22. Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, and Yota Otachi: Parameterized complexity of (A,l)-path packing, Proceedings of the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020), pp. 43--55.
  23. Tibor Jordán, Yusuke Kobayashi, Ryoga Mahara, and Kazuhisa Makino: The Steiner problem for count matroids, Proceedings of the 31st International Workshop on Combinatorial Algorithms (IWOCA 2020), pp. 330--342.
  24. Yusuke Kobayashi: Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles, Proceedings of the 21st Conference on Integer Programming and Combinatorial Optimization (IPCO 2020), pp. 280--293.
  25. Yusuke Kobayashi: An FPT algorithm for minimum additive spanner problem, Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 11:1--11:16.
  26. Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, and Kunihiro Wasa: Shortest reconfiguration of colorings under Kempe-changes, Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 35:1--35:14.
  27. Yoichi Iwata and Yusuke Kobayashi: Improved analysis of highest-degree branching for feedback vertex set, Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), 22:1--22:11.
  28. Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, and Yusuke Kobayashi: Parameterized algorithms for maximum cut with connectivity constraints, Proceedings of the 14th International Symposium on Parameterized and Exact Computation (IPEC 2019), 13:1--13:15.
  29. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Shortest reconfiguration of perfect matchings via alternating cycles, Proceedings of the 27th European Symposium on Algorithms (ESA 2019), 61:1--61:15.
  30. Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa: The perfect matching reconfiguration problem, Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019), 80:1--80:14.
  31. Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, and Kunihiro Wasa: Diameter of colorings under Kempe changes, Proceedings of the 25th Annual International Computing and Combinatorics Conference (COCOON 2019), pp. 52--64.
  32. Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, and Suguru Tamaki: An improved fixed-parameter algorithm for max-cut parameterized by crossing number, Proceedings of the 30th International Workshop on Combinatorial Algorithms (IWOCA 2019), pp. 327--338. IWOCA 2019 Best Paper Award
  33. Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Algorithms for gerrymandering over graphs, Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), pp. 1413--1421.
  34. Koki Takayama and Yusuke Kobayashi: A strongly polynomial time algorithm for the maximum supply rate problem on trees, Proceedings of the 12th International Frontiers of Algorithmics Workshop (FAW 2018), pp. 54--67.
  35. Takehiro Ito, Naonori Kakimura, and Yusuke Kobayashi: Complexity of the multi-service center problem, Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), 48:1--48:12.
  36. Kristóf Bérczi and Yusuke Kobayashi: The directed disjoint shortest paths problem, Proceedings of the 25th European Symposium on Algorithms (ESA 2017), 13:1--13:13.
  37. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto, and Taichi Shiitada: Tight approximability of the server allocation problem for real-time applications, Proceedings of the 3rd International Workshop on Algorithmic Aspects of Cloud Computing (Algocloud 2017), pp. 41--55.
  38. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Reconfiguration of maximum-weight b-matchings in a graph, Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017), pp. 287--296.
  39. Satoru Iwata and Yusuke Kobayashi: A weighted linear matroid parity algorithm, Proceedings of the 49th ACM Symposium on Theory of Computing (STOC 2017), 2017, pp. 264--276. STOC 2017 Best Paper Award
  40. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Efficient stabilization of cooperative matching games, Proceedings of the 15th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2016), 2016, pp. 41--49.
  41. Yusuke Kobayashi and Kenjiro Takazawa: Randomized strategies for cardinality robustness in the knapsack problem, Proceedings of the 13th Meeting on Analytic Algorithmics and Combinatorics (ANALCO 2016), 2016, pp. 25--33.
    We found a mathematical error in Section 3.3, and this section is removed in the journal version.
  42. Yasushi Kawase, Yusuke Kobayashi, and Yutaro Yamaguchi: Finding a path in group-labeled graphs with two labels forbidden, Proceedings of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), 2015, pp. 797--809.
  43. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Minimum-cost b-edge dominating sets on trees, Proceedings of the 25th International Symposium on Algorithms and Computation (ISAAC 2014), LNCS 8889, 2014, pp. 195--207.
  44. Ken-ichi Kawarabayashi, Yusuke Kobayashi, and Stephan Kreutzer: An excluded half-integral grid theorem for digraphs and the directed disjoint paths problem, Proceedings of the 46th ACM Symposium on Theory of Computing (STOC 2014), 2014, pp. 70--78.
  45. Yusuke Kobayashi and Kensuke Otsuki: Max-flow min-cut theorem and faster algorithms in a circular disk failure model, Proceedings of the 33rd Annual IEEE International Conference on Computer Communications (INFOCOM 2014), 2014, pp. 1635--1643.
  46. Attila Bernáth and Yusuke Kobayashi: The generalized terminal backup problem, Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), 2014, pp. 1678--1686.
  47. Ken-ichi Kawarabayashi and Yusuke Kobayashi: All-or-nothing multicommodity flow problem with bounded fractionality in planar graphs, Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2013), 2013, pp. 187--196.
  48. Akitoshi Kawamura and Yusuke Kobayashi: Fence patrolling by mobile agents with distinct speeds, Proceedings of the 23rd International Symposium on Algorithms and Computation (ISAAC 2012), LNCS 7676, 2012, pp. 598--608.
  49. Ken-ichi Kawarabayashi and Yusuke Kobayashi: Linear min-max relation between the treewidth of H-minor-free graphs and its largest grid minor, Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS 2012), 2012, pp. 278--289.
  50. Ken-ichi Kawarabayashi and Yusuke Kobayashi: Edge-disjoint odd cycles in 4-edge-connected graphs, Proceedings of the 29th Symposium on Theoretical Aspects of Computer Science (STACS 2012), 2012, pp. 206--217.
  51. Ken-ichi Kawarabayashi and Yusuke Kobayashi: List-coloring graphs without subdivisions and without immersions, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 2012, pp. 1425--1435.
  52. Naonori Kakimura, Ken-ichi Kawarabayashi, and Yusuke Kobayashi: Erdős-Pósa property and its algorithmic applications --- parity constraints, subset feedback set, and subset packing, Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2012), 2012, pp. 1726--1736.
  53. Yusuke Kobayashi and Yuichi Yoshida: Algorithms for finding a maximum non-k-linked graph, Proceedings of the 19th European Symposium on Algorithms (ESA 2011), LNCS 6942, 2011, pp. 131--142.
  54. Ken-ichi Kawarabayashi and Yusuke Kobayashi: Breaking O(n^{1/2})-approximation algorithms for the edge-disjoint paths problem with congestion two, Proceedings of the 43rd ACM Symposium on Theory of Computing (STOC 2011), 2011, pp. 81--88.
  55. Ryo Fujita, Yusuke Kobayashi, and Kazuhisa Makino: Robust matchings and matroid intersections, Proceedings of the 18th Annual European Symposium on Algorithms (ESA 2010), LNCS 6347, 2010, pp. 123--134.
  56. Ken-ichi Kawarabayashi and Yusuke Kobayashi: Improved algorithm for the half-disjoint paths problem, Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010), LNCS 6302, 2010, pp. 287--297.
  57. Ken-ichi Kawarabayashi and Yusuke Kobayashi: An O(log n)-approximation algorithm for the disjoint paths problem in Eulerian planar graphs and 4-edge-connected planar graphs, Proceedings of the 13th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2010), LNCS 6302, 2010, pp. 274--286.
  58. Ken-ichi Kawarabayashi and Yusuke Kobayashi: The edge disjoint paths problem in Eulerian graphs and 4-edge-connected graphs, Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), 2010, pp. 345--353.
  59. Yusuke Kobayashi and Christian Sommer: On shortest disjoint paths in planar graphs, Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC 2009), LNCS 5878, 2009, pp. 293--302.
  60. Shinji Imahori, Yuichiro Miyamoto, Hideki Hashimoto, Yusuke Kobayashi, Mihiro Sasaki, and Mutsunori Yagiura: The complexity of the node capacitated in-tree packing problem, Proceedings of the International Network Optimization Conference 2009, 2009.
  61. Yusuke Kobayashi and Ken-ichi Kawarabayashi: Algorithms for finding an induced cycle in planar graphs and bounded genus graphs, Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), 2009, pp. 1146--1155.
  62. Ken-ichi Kawarabayashi and Yusuke Kobayashi: The induced disjoint paths problem, Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO 2008), LNCS 5035, 2008, pp. 47--61.

Preprints

  1. Yuni Iwamasa, Yusuke Kobayashi, and Kenjiro Takazawa: Finding a maximum restricted t-matching via Boolean edge-CSP, arXiv:2310.20245, 2023.
  2. Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, and Akira Suzuki: Reconfiguration of time-respecting arborescences, arXiv:2305.07262, 2023.
  3. Yusuke Kobayashi, Ryoga Mahara, and Souta Sakamoto: EFX allocations for indivisible chores: matching-based approach, arXiv:2305.04168, 2023.
  4. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Algorithmic theory of qubit routing, arXiv:2305.02059, 2023.
  5. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, and Yoshio Okamoto: Hardness of finding combinatorial shortest paths on graph associahedra, arXiv:2304.14782, 2023.
  6. Yusuke Kobayashi and Takashi Noguchi: An approximation algorithm for two-edge-connected subgraph problem via triangle-free two-edge-cover, arXiv:2304.13228, 2023.
  7. Yusuke Kobayashi, Ryoga Mahara, Tamás Schwarcz: Reconfiguration of the union of arborescences, arXiv:2304.13217, 2023.
  8. Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki: Reconfiguration of colorings in triangulations of the sphere, arXiv:2210.17105, 2022.
  9. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki: Rerouting planar curves and disjoint paths, arXiv:2210.11778, 2022.
  10. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki: On reachable assignments under dichotomous preferences, arXiv:2209.10262, 2022.
  11. Yusuke Kobayashi: Optimal general factor problem and jump system intersection, arXiv:2209.00779, 2022.
  12. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki: Reforming an envy-free matching, arXiv:2207.02641, 2022.
  13. Yusuke Kobayashi and Ryoga Mahara: Proportional allocation of indivisible goods up to the least valued good on average, arXiv:2205.00236, 2022.
  14. Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, and Yota Otachi: A framework to design approximation algorithms for finding diverse solutions in combinatorial problems, arXiv:2201.08940, 2022.
  15. Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa: Reconfiguration of spanning trees with degree constraint or diameter constraint, arXiv:2201.04354, 2022.
  16. Asei Inoue and Yusuke Kobayashi: An additive approximation scheme for the Nash social welfare maximization with identical additive valuations, arXiv:2201.01419, 2022.
  17. Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki: Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams, arXiv:2110.11585, 2021.
  18. Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, and Yota Otachi: An improved deterministic parameterized algorithm for cactus vertex deletion, arXiv:2012.04910, 2020.
  19. Kristóf Bérczi, Naonori Kakimura, and Yusuke Kobayashi: Market pricing for matroid rank valuations, arXiv:2007.08759, 2020.
  20. Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Daniel Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, and Uéverton S. Souza: Computing the largest bond and the maximum connected cut of a graph, arXiv:2007.04513, 2020.
  21. Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, and Kunihiro Wasa: Reconfiguration of spanning trees with many or few leaves, arXiv:2006.14309, 2020.
  22. Kristóf Bérczi, Erika R. Bérczi-Kovács, Endre Boros, Fekadu Tolessa Gedefa, Naoyuki Kamiyama, Telikepalli Kavitha, Yusuke Kobayashi, and Kazuhisa Makino: Envy-free relaxations for goods, chores, and mixed items, arXiv:2006.04428, 2020.
  23. Yusuke Kobayashi: Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles, arXiv:1911.06436, 2019.
  24. Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Yushi Uno: Linear-time recognition of double-threshold graphs, arXiv:1909.09371, 2019.
  25. Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, and Yusuke Kobayashi: Parameterized algorithms for maximum cut with connectivity constraints, arXiv:1908.03389, 2019.
  26. Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto: Shortest reconfiguration of perfect matchings via alternating cycles, arXiv:1907.01700, 2019.
  27. Yoichi Iwata and Yusuke Kobayashi: Improved analysis of highest-degree branching for feedback vertex set, arXiv:1905.12233, 2019.
  28. Satoru Iwata and Yusuke Kobayashi: A weighted linear matroid parity algorithm, arXiv:1905.13371, 2019. (Old version: METR 2017-01, University of Tokyo (2017))
  29. Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Tom C. van der Zanden: Subgraph isomorphism on graph classes that exclude a substructure, arXiv:1905.10670, 2019.
  30. Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, and Kunihiro Wasa: The perfect matching reconfiguration problem, arXiv:1904.06184, 2019.
  31. Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, and Suguru Tamaki: An FPT algorithm for max-cut parameterized by crossing number, arXiv:1904.05011, 2019.
  32. Yusuke Kobayashi: An FPT algorithm for minimum additive spanner problem, arXiv:1903.01047, 2019.
  33. Yasushi Kawase, Yusuke Kobayashi, and Yutaro Yamaguchi: Tight approximation for unconstrained XOS maximization, arXiv:1811.09045, 2018.
  34. Yasushi Kawase, Yusuke Kobayashi, and Yutaro Yamaguchi: Finding a path in group-labeled graphs with two labels forbidden, arXiv:1807.00109, 2018.
  35. Kristóf Bérczi and Yusuke Kobayashi: The directed disjoint shortest paths problem, TR-2016-13, Egervary Research Group, Budapest (2016).
  36. Kristóf Bérczi and Yusuke Kobayashi: An algorithm for identifying cycle-plus-triangles graphs, TR-2016-12, Egervary Research Group, Budapest (2016).
  37. Yusuke Kobayashi and Kenjiro Takazawa: Randomized strategies for cardinality robustness in the knapsack problem, RIMS Preprint, RIMS-1833, 2015.
  38. Kristóf Bérczi, Tamás Király, and Yusuke Kobayashi: Algorithmic aspects of covering supermodular functions under matroid constraints, TR-2015-05, Egervary Research Group, Budapest (2015).
  39. Yusuke Kobayashi and Sho Toyooka: Finding a shortest non-zero path in group-labeled graphs, METR 2015-19, University of Tokyo (2015).
  40. Kensuke Otsuki, Yusuke Kobayashi, and Kazuo Murota: Improved max-flow min-cut algorithms in a circular disk failure model with application to a road network, METR 2015-13, University of Tokyo (2015).
  41. Hiroshi Nishiyama, Yusuke Kobayashi, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita: The parity Hamiltonian cycle problem, arXiv:1501.06323, 2015.
  42. Yusuke Kobayashi: The complexity of maximizing the difference of two matroid rank functions, METR 2014-42, University of Tokyo (2014).
  43. Yasushi Kawase, Yusuke Kobayashi, and Yutaro Yamaguchi: Finding a path in group-labeled graphs with two labels forbidden, METR 2014-41, University of Tokyo (2014).
  44. Kristóf Bérczi, Tamás Király, and Yusuke Kobayashi: Covering intersecting bi-set families under matroid constraints, TR-2013-06, Egervary Research Group, Budapest (2013).
  45. Attila Bernáth, Yusuke Kobayashi, and Tatsuya Matsuoka: The generalized terminal backup problem, TR-2013-07, Egervary Research Group, Budapest (2013). (See also METR 2013-25, University of Tokyo (2013).)
  46. Yusuke Kobayashi and Kensuke Otsuki: Max-flow min-cut theorem and faster algorithms in a circular disk failure model, METR 2013-15, University of Tokyo (2013).
  47. Kota Ishihara and Yusuke Kobayashi: Routing algorithms under mutual interference constraints, METR 2013-14, University of Tokyo (2013).
  48. Yusuke Kobayashi: Triangle-free 2-matchings and M-concave functions on jump systems, METR 2013-06, University of Tokyo (2013).
  49. Yusuke Kobayashi and Yuichi Yoshida: Algorithms for finding a maximum non-k-linked graph, METR 2011-23, University of Tokyo (2011).
  50. Yusuke Kobayashi and Xin Yin: An algorithm for finding a maximum t-matching excluding complete partite subgraphs, METR 2011-12, University of Tokyo (2011).
  51. Ryo Fujita, Yusuke Kobayashi, and Kazuhisa Makino: Robust matchings and matroid intersections, METR 2010-20, University of Tokyo (2010).
  52. Yusuke Kobayashi, Jácint Szabó, and Kenjiro Takazawa: A proof to Cunningham's conjecture on restricted subgraphs and jump systems, TR-2010-04, Egervary Research Group, Budapest (2010).
  53. Yusuke Kobayashi and Christian Sommer: On shortest disjoint paths in planar graphs, METR 2009-38, University of Tokyo (2009).
  54. Yusuke Kobayashi, Kazuo Murota, and Robert Weismantel: Cone superadditivity of discrete convex functions, METR 2009-30, University of Tokyo (2009).
  55. Shinji Imahori, Yuichiro Miyamoto, Hideki Hashimoto, Yusuke Kobayashi, Mihiro Sasaki, and Mutsunori Yagiura: The complexity of the node capacitated in-tree packing problem, METR 2009-29, University of Tokyo (2009).
  56. Yusuke Kobayashi: A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs, METR 2009-26, University of Tokyo (2009).
  57. Kristóf Bérczi and Yusuke Kobayashi: An algorithm for (n-3)-connectivity augmentation problem: jump system approach, METR 2009-12, University of Tokyo (2009). [revised version]
  58. Yusuke Kobayashi and Kenjiro Takazawa: Square-free 2-matchings in bipartite graphs and jump systems, METR 2008-40, University of Tokyo (2008). (See also RIMS Preprint, RIMS-1640, 2008.)
  59. Ken-ichi Kawarabayashi and Yusuke Kobayashi: Algorithms for finding an induced cycle in planar graphs, METR 2008-23, University of Tokyo (2008).
  60. Yusuke Kobayashi and Kenjiro Takazawa: Even factors, jump systems, and discrete convexity, METR 2007-36, University of Tokyo (2007). (See also RIMS Preprint, RIMS-1595, 2007.)
  61. Yusuke Kobayashi: An extension of the disjoint paths problem, METR 2007-14, University of Tokyo (2007).
  62. Yusuke Kobayashi and Kazuo Murota: Induction of M-convex functions by linking systems, METR 2006-43, University of Tokyo (2006).
  63. Yusuke Kobayashi, Kazuo Murota, and Ken'ichiro Tanaka: Operations on M-convex functions on jump systems, METR 2006-13, University of Tokyo (2006).
  64. Naonori Kakimura and Yusuke Kobayashi: On odd-cycle-symmetry of digraphs, METR 2005-36, University of Tokyo (2005).
  65. Satoru Iwata and Yusuke Kobayashi: An algorithm for minimum cost arc-connectivity orientations, METR 2005-16, University of Tokyo (2005).

(See: METR (Mathematical Engineering Technical Reports) )

Theses

Others (in Japanese)

  1. 小林佑輔: グラフマイナー理論, 数理科学, No.702 (2021年12月号), サイエンス社，pp. 30--36.
  2. 小林佑輔: グラフ・ネットワークにおける最適化, 数理科学, No.677 (2019年11月号), サイエンス社，pp. 14--20.
  3. 山本芳嗣（編著）: 基礎数学IV．最適化理論, 東京化学同人．（担当：3.3節，4.1節）
  4. 小林佑輔: マッチングからマトロイドパリティへ, 電子情報通信学会誌, Vol.101 No.3 (2018年3月), pp. 248--252.
  5. 小林佑輔，福永拓郎: 通信ネットワークのモデル化と最適化, オペレーションズ・リサーチ, Vol.60 No.8 (2015年8月号), pp. 443--448.
Return to Home
トップページへ