Publications of Yusuke Kobayashi

Journal Articles

  1. Kristóf Bérczi and Yusuke Kobayashi: An algorithm for identifying cycle-plus-triangles graphs, Discrete Applied Mathematics, to appear.
  2. Yusuke Kobayashi and Kenjiro Takazawa: Randomized strategies for cardinality robustness in the knapsack problem, Theoretical Computer Science, to appear.
  3. 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.
  4. 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.
  5. Yusuke Kobayashi and Sho Toyooka: Finding a shortest non-zero path in group-labeled graphs via permanent computation, Algorithmica, 77 (2017), pp. 1128--1142.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. Attila Bernáth, Yusuke Kobayashi, and Tatsuya Matsuoka: The generalized terminal backup problem, SIAM Journal on Discrete Mathematics, 29 (2015), pp. 1764--1782.
  11. Kota Ishihara and Yusuke Kobayashi: Routing algorithms under mutual interference constraints, Journal of the Operations Research Society of Japan, 58 (2015), pp. 209--222.
  12. Yusuke Kobayashi: The complexity of minimizing the difference of two M${}^\natural$-convex set functions, Operations Research Letters, 43 (2015), pp. 573--574.
  13. 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.
  14. 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.
  15. Akitoshi Kawamura and Yusuke Kobayashi: Fence patrolling by mobile agents with distinct speeds, Distributed Computing, 28 (2015), pp. 147--154.
  16. Yusuke Kobayashi: Triangle-free 2-matchings and M-concave functions on jump systems, Discrete Applied Mathematics, 175 (2014), pp. 35--42.
  17. Ryo Fujita, Yusuke Kobayashi, and Kazuhisa Makino: Robust matchings and matroid intersections, SIAM Journal on Discrete Mathematics, 27 (2013), pp. 1234--1256.
  18. 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.
  19. Yusuke Kobayashi, Kazuo Murota, and Robert Weismantel: Cone superadditivity of discrete convex functions, Mathematical Programming, Series A, 135 (2012), pp. 25--44.
  20. 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.
  21. 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.
  22. Yusuke Kobayashi and Yuichi Yoshida: Algorithms for finding a maximum non-k-linked graph, SIAM Journal on Discrete Mathematics, 26 (2012), pp. 591--604.
  23. Yusuke Kobayashi and Xin Yin: An algorithm for finding a maximum t-matching excluding complete partite subgraphs, Discrete Optimization, 9 (2012), pp. 98--108.
  24. Yuichi Yoshida and Yusuke Kobayashi: Testing the (s,t)-disconnectivity of graphs and digraphs, Theoretical Computer Science, 434 (2012), pp. 98--113.
  25. Ken-ichi Kawarabayashi and Yusuke Kobayashi: An immersion of a square in $4$-edge-connected graphs, Progress in Informatics, 9 (2012), pp. 35--36.
  26. 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.
  27. 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.
  28. 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.
  29. 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.
  30. 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.
  31. Ken-ichi Kawarabayashi and Yusuke Kobayashi: Algorithms for finding an induced cycle in planar graphs, Combinatorica, 30 (2010), pp. 715--734.
  32. Yusuke Kobayashi and Christian Sommer: On shortest disjoint paths in planar graphs, Discrete Optimization, 7 (2010), pp. 234--245.
  33. Yusuke Kobayashi: A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs, Discrete Optimization, 7 (2010), pp. 197--202.
  34. Satoru Iwata and Yusuke Kobayashi: An algorithm for minimum cost arc-connectivity orientations, Algorithmica, 56 (2010), pp. 437--447.
  35. Yusuke Kobayashi: Induced disjoint paths problem in a planar digraph, Discrete Applied Mathematics, 157 (2009), pp. 3231--3238.
  36. Yusuke Kobayashi and Kenjiro Takazawa: Even factors, jump systems, and discrete convexity, Journal of Combinatorial Theory, Series B, 99 (2009), pp. 139--161.
  37. Yusuke Kobayashi and Kazuo Murota: Induction of M-convex functions by linking systems, Discrete Applied Mathematics, 155 (2007), pp. 1471--1480.
  38. 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. Kristóf Bérczi and Yusuke Kobayashi: The directed disjoint shortest paths problem, Proceedings of the 25th European Symposium on Algorithms (ESA 2017), to appear.
  2. 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), to appear.
  3. 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.
  4. 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. [full version] STOC 2017 Best Paper Award
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. Naonori Kakimura, Ken-ichi Kawarabayashi, and Yusuke Kobayashi: Erd\H{o}s-P\'osa 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.
  18. 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.
  19. 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.
  20. 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.
  21. 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.
  22. 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.
  23. 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.
  24. 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.
  25. 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.
  26. 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.
  27. 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.

Other Conference Proceedings

  1. Satoru Iwata and Yusuke Kobayashi: Weighted linear matroid parity problem, Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2017, pp. 21--24.
  2. Yusuke Kobayashi and Yutaro Yamaguchi: On applications of weighted linear matroid parity, Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2017, pp. 363--372.
  3. Yusuke Kobayashi and Sho Toyooka: Finding a shortest non-zero path in group-labeled graphs, Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2015, pp. 318--322.
  4. Kristóf Bérczi, Tamás Király, and Yusuke Kobayashi: Algorithmic aspects of covering supermodular functions under matroid constraints, Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2015, pp. 301--306.
  5. Yusuke Kobayashi: Triangle-free 2-matchings and M-concave functions on jump systems, Proceedings of the 8th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2013, pp. 383--386.
  6. Yusuke Kobayashi and Xin Yin: An algorithm for finding a maximum t-matching excluding complete partite subgraphs, Proceedings of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2011, pp. 494--502.
  7. Yusuke Kobayashi, Kazuo Murota, and Robert Weismantel: Cone superadditivity of discrete convex functions, Proceedings of the 7th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2011, pp. 264--273.
  8. Yusuke Kobayashi and Kenjiro Takazawa: Square-free 2-matchings in bipartite graphs and jump systems, Proceedings of the 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications, 2009, pp. 187--197.
  9. Yusuke Kobayashi, Kazuo Murota, and Ken'ichiro Tanaka: Operations on M-convex functions on jump systems, Proceedings of the 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, 2007, pp. 166--175.

Technical Reports

  1. Satoru Iwata and Yusuke Kobayashi: A weighted linear matroid parity algorithm, METR 2017-01, University of Tokyo (2017). [PDF]
  2. Kristóf Bérczi and Yusuke Kobayashi: The directed disjoint shortest paths problem, TR-2016-13, Egervary Research Group, Budapest (2016).
  3. Kristóf Bérczi and Yusuke Kobayashi: An algorithm for identifying cycle-plus-triangles graphs, TR-2016-12, Egervary Research Group, Budapest (2016).
  4. Yusuke Kobayashi and Kenjiro Takazawa: Randomized strategies for cardinality robustness in the knapsack problem, RIMS Preprint, RIMS-1833, 2015.
  5. 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).
  6. Yusuke Kobayashi and Sho Toyooka: Finding a shortest non-zero path in group-labeled graphs, METR 2015-19, University of Tokyo (2015).
  7. 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).
  8. Hiroshi Nishiyama, Yusuke Kobayashi, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita: The parity Hamiltonian cycle problem, arXiv:1501.06323, 2015.
  9. Yusuke Kobayashi: The complexity of maximizing the difference of two matroid rank functions, METR 2014-42, University of Tokyo (2014).
  10. 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).
  11. 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).
  12. 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).)
  13. 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).
  14. Kota Ishihara and Yusuke Kobayashi: Routing algorithms under mutual interference constraints, METR 2013-14, University of Tokyo (2013).
  15. Yusuke Kobayashi: Triangle-free 2-matchings and M-concave functions on jump systems, METR 2013-06, University of Tokyo (2013).
  16. Yusuke Kobayashi and Yuichi Yoshida: Algorithms for finding a maximum non-k-linked graph, METR 2011-23, University of Tokyo (2011).
  17. Yusuke Kobayashi and Xin Yin: An algorithm for finding a maximum t-matching excluding complete partite subgraphs, METR 2011-12, University of Tokyo (2011).
  18. Ryo Fujita, Yusuke Kobayashi, and Kazuhisa Makino: Robust matchings and matroid intersections, METR 2010-20, University of Tokyo (2010).
  19. 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).
  20. Yusuke Kobayashi and Christian Sommer: On shortest disjoint paths in planar graphs, METR 2009-38, University of Tokyo (2009).
  21. Yusuke Kobayashi, Kazuo Murota, and Robert Weismantel: Cone superadditivity of discrete convex functions, METR 2009-30, University of Tokyo (2009).
  22. 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).
  23. Yusuke Kobayashi: A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs, METR 2009-26, University of Tokyo (2009).
  24. 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]
  25. 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.)
  26. Ken-ichi Kawarabayashi and Yusuke Kobayashi: Algorithms for finding an induced cycle in planar graphs, METR 2008-23, University of Tokyo (2008).
  27. 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.)
  28. Yusuke Kobayashi: An extension of the disjoint paths problem, METR 2007-14, University of Tokyo (2007).
  29. Yusuke Kobayashi and Kazuo Murota: Induction of M-convex functions by linking systems, METR 2006-43, University of Tokyo (2006).
  30. Yusuke Kobayashi, Kazuo Murota, and Ken'ichiro Tanaka: Operations on M-convex functions on jump systems, METR 2006-13, University of Tokyo (2006).
  31. Naonori Kakimura and Yusuke Kobayashi: On odd-cycle-symmetry of digraphs, METR 2005-36, University of Tokyo (2005).
  32. 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. 小林佑輔,福永拓郎: 通信ネットワークのモデル化と最適化, オペレーションズ・リサーチ, Vol.60 No.8 (2015年8月号), pp. 443--448.

Return to Home
トップページへ