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, and Yoshio Okamoto: Reconfiguration of maximum-weight b-matchings in a graph, Proceedings of the 23rd Annual International Computing and Combinatorics Conference (COCOON 2017), to appear.
  3. 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
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. 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.
  11. 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.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 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.
  19. 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.
  20. 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.
  21. 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.
  22. 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.
  23. 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.
  24. 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.
  25. 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.
  26. 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
トップページへ