Publications of Yusuke Kobayashi
Journal Articles
- Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki:
Reconfiguration of colorings in triangulations of the sphere,
Journal of Computational Geometry, to appear.
- Yusuke Kobayashi, Ryoga Mahara, and Tamás Schwarcz:
Reconfiguration of the union of arborescences,
Algorithmica, to appear.
- Asei Inoue and Yusuke Kobayashi:
An additive approximation scheme for the Nash social welfare maximization with identical additive valuations,
Journal of the Operations Research Society of Japan, to appear.
- Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto:
Algorithmic theory of qubit routing in the linear nearest neighbor architectures,
ACM Transactions on Quantum Computing, to appear.
- Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki:
Rerouting planar curves and disjoint paths,
ACM Transactions on Algorithms, 21 (2025), Article 20.
- Yusuke Kobayashi and Ryoga Mahara:
Proportional allocation of indivisible goods up to the least valued good on average,
SIAM Journal on Discrete Mathematics, 39 (2025), pp. 533--549.
- Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, and Kenta Ozeki:
Reforming an envy-free matching,
Algorithmica, 87 (2025), pp. 594--620.
- Yusuke Kobayashi:
Optimal general factor problem and jump system intersection,
Mathematical Programming, Series B, 210 (2025), pp. 591--610.
- Yusuke Kobayashi, Ryoga Mahara, and Souta Sakamoto:
EFX allocations for indivisible chores: matching-based approach,
Theoretical Computer Science, 1026 (2025), 115010.
- 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,
Theoretical Computer Science, 1002 (2024), 114596.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Satoru Iwata and Yusuke Kobayashi:
A weighted linear matroid parity algorithm,
SIAM Journal on Computing, 51 (2022), pp. STOC17-238--STOC17-280.
- 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.
- Yusuke Kobayashi:
Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles,
Mathematical Programming, Series B, 192 (2022), pp. 675--702.
- Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Yushi Uno,
Linear-time recognition of double-threshold graphs,
Algorithmica, 84 (2022), pp. 1163--1181.
- 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.
- 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.
- Yuval Filmus, Yasushi Kawase, Yusuke Kobayashi, and Yutaro Yamaguchi:
Tight approximation for unconstrained XOS maximization,
Mathematics of Operations Research, 46 (2021), pp. 1599--1610.
- Yoichi Iwata and Yusuke Kobayashi:
Improved analysis of highest-degree branching for feedback vertex set,
Algorithmica, 83 (2021), pp. 2503--2520.
- Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto:
Algorithms for gerrymandering over graphs,
Theoretical Computer Science, 868 (2021), pp. 30--45.
- 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.
- 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.
- Takehiro Ito, Naonori Kakimura, and Yusuke Kobayashi:
Complexity of the multi-service center problem,
Theoretical Computer Science, 842 (2020), pp. 18--27.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Yusuke Kobayashi and Ryo Sako:
Two disjoint shortest paths problem with non-negative edge length,
Operations Research Letters, 47 (2019), pp. 66--69.
- 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.
- Yusuke Kobayashi:
NP-hardness and fixed-parameter tractability of the minimum spanner problem,
Theoretical Computer Science, 746 (2018), pp. 88--97.
- 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.
- 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.
- Hiroshi Nishiyama, Yusuke Kobayashi, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita:
The parity Hamiltonian cycle problem,
Discrete Mathematics, 341 (2018), pp. 606--626.
- Yusuke Kobayashi and Kenjiro Takazawa:
Randomized strategies for cardinality robustness in the knapsack problem,
Theoretical Computer Science, 699 (2017), pp. 53--62.
- Kristóf Bérczi and Yusuke Kobayashi:
An algorithm for identifying cycle-plus-triangles graphs,
Discrete Applied Mathematics, 226 (2017), pp. 10--16.
- 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.
- 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.
- Yusuke Kobayashi and Sho Toyooka:
Finding a shortest non-zero path in group-labeled graphs via permanent computation,
Algorithmica, 77 (2017), pp. 1128--1142.
- 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.
- 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.
- 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.
- 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.
- Attila Bernáth, Yusuke Kobayashi, and Tatsuya Matsuoka:
The generalized terminal backup problem,
SIAM Journal on Discrete Mathematics, 29 (2015), pp. 1764--1782.
- Kota Ishihara and Yusuke Kobayashi:
Routing algorithms under mutual interference constraints,
Journal of the Operations Research Society of Japan, 58 (2015), pp. 209--222.
- Yusuke Kobayashi:
The complexity of minimizing the difference of two M♮-convex set functions,
Operations Research Letters, 43 (2015), pp. 573--574.
- 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.
- 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.
- Akitoshi Kawamura and Yusuke Kobayashi:
Fence patrolling by mobile agents with distinct speeds,
Distributed Computing, 28 (2015), pp. 147--154.
- Yusuke Kobayashi:
Triangle-free 2-matchings and M-concave functions on jump systems,
Discrete Applied Mathematics, 175 (2014), pp. 35--42.
- Ryo Fujita, Yusuke Kobayashi, and Kazuhisa Makino:
Robust matchings and matroid intersections,
SIAM Journal on Discrete Mathematics,
27 (2013), pp. 1234--1256.
- 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.
- Yusuke Kobayashi, Kazuo Murota, and Robert Weismantel:
Cone superadditivity of discrete convex functions,
Mathematical Programming, Series A, 135 (2012), pp. 25--44.
- 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.
- 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.
- Yusuke Kobayashi and Yuichi Yoshida:
Algorithms for finding a maximum non-k-linked graph,
SIAM Journal on Discrete Mathematics, 26 (2012), pp. 591--604.
- Yusuke Kobayashi and Xin Yin:
An algorithm for finding a maximum t-matching excluding complete partite subgraphs,
Discrete Optimization, 9 (2012), pp. 98--108.
- Yuichi Yoshida and Yusuke Kobayashi:
Testing the (s,t)-disconnectivity of graphs and digraphs,
Theoretical Computer Science, 434 (2012), pp. 98--113.
- Ken-ichi Kawarabayashi and Yusuke Kobayashi:
An immersion of a square in 4-edge-connected graphs,
Progress in Informatics, 9 (2012), pp. 35--36.
- 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.
- 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.
- 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.
- 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.
- 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.
- Ken-ichi Kawarabayashi and Yusuke Kobayashi:
Algorithms for finding an induced cycle in planar graphs,
Combinatorica, 30 (2010), pp. 715--734.
- Yusuke Kobayashi and Christian Sommer:
On shortest disjoint paths in planar graphs,
Discrete Optimization, 7 (2010), pp. 234--245.
- Yusuke Kobayashi:
A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs,
Discrete Optimization, 7 (2010), pp. 197--202.
- Satoru Iwata and Yusuke Kobayashi:
An algorithm for minimum cost arc-connectivity orientations,
Algorithmica, 56 (2010), pp. 437--447.
- Yusuke Kobayashi:
Induced disjoint paths problem in a planar digraph,
Discrete Applied Mathematics, 157 (2009), pp. 3231--3238.
- Yusuke Kobayashi and Kenjiro Takazawa:
Even factors, jump systems, and discrete convexity,
Journal of Combinatorial Theory, Series B, 99 (2009), pp. 139--161.
- Yusuke Kobayashi and Kazuo Murota:
Induction of M-convex functions by linking systems,
Discrete Applied Mathematics, 155 (2007), pp. 1471--1480.
- 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
- Akitoshi Kawamura, Yusuke Kobayashi, and Yosuke Kusano:
Pinwheel covering,
Proceedings of the 14th International Conference on Algorithms and Complexity (CIAC 2025), to appear.
- Yusuke Kobayashi and Takashi Noguchi:
Validating a PTAS for triangle-free 2-matching via a simple decomposition theorem,
Proceedings of SIAM Symposium on Simplicity in Algorithms (SOSA 2025), 2025, pp. 281--289.
- Yuni Iwamasa, Yusuke Kobayashi, and Kenjiro Takazawa:
Finding a maximum restricted t-matching via Boolean edge-CSP,
Proceedings of the 32nd European Symposium on Algorithms (ESA 2024), 2024, 75:1--75:15.
- Yusuke Kobayashi and Tatsuya Terao:
Subquadratic submodular maximization with a general matroid constraint,
Proceedings of the 51st EATCS International Colloquium on Automata, Languages and Programming (ICALP 2024), 2024, 100:1--100:19.
- 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), 2023, 44:1--44:14.
- 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), 2023, 43:1--43:10.
- 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), 2023, pp. 257--270.
- 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), 2023, pp. 533--546.
- 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), 2023, pp. 521--532.
- 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), 2023, 82:1--82:17.
- 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), 2023, 81:1--81:19.
- Yusuke Kobayashi:
Optimal general factor problem and jump system intersection,
Proceedings of the 24th Conference on Integer Programming and Combinatorial Optimization (IPCO 2023), 2023, pp. 291--305.
- 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), 2023, 43:1--43:16.
- 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), 2023, pp. 3968--3976.
- 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), 2022, 55:1--55:13.
- 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), 2022, 47:1--47:15.
- 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), 2022, pp. 650--658.
- 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), 2022, pp. 341--354.
- 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), 2022,
pp. 5084--5091.
- 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), 2022, 15:1--15:21.
- 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), 2022, pp. 1342--1355.
- 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), 2020, 15:1--15:15.
- 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), 2020, 39:1--39:15.
- 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), 2020, 24:1--24:15.
- 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), 2020, pp. 286--297.
- 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), 2020, pp. 43--55.
- 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), 2020, pp. 330--342.
- 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), 2020, pp. 280--293.
- Yusuke Kobayashi:
An FPT algorithm for minimum additive spanner problem,
Proceedings of the 37th Symposium on Theoretical Aspects of Computer Science (STACS 2020), 2020, 11:1--11:16.
- 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), 2020, 35:1--35:14.
- 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), 2019, 22:1--22:11.
- 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), 2019, 13:1--13:15.
- 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), 2019, 61:1--61:15.
- 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), 2019, 80:1--80:14.
- 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), 2019, pp. 52--64.
- 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), 2019, pp. 327--338.
IWOCA 2019 Best Paper Award
- 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), 2019, pp. 1413--1421.
- 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), 2018, pp. 54--67.
- 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), 2017, 48:1--48:12.
- Kristóf Bérczi and Yusuke Kobayashi:
The directed disjoint shortest paths problem,
Proceedings of the 25th European Symposium on Algorithms (ESA 2017), 2017, 13:1--13:13.
- 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), 2017,
pp. 41--55.
- 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), 2017,
pp. 287--296.
- 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
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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
- Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto:
Loss minimization for electrical flows over spanning trees on grids,
arXiv:2412.14583, 2024.
- Yusuke Kobayashi and Takashi Noguchi:
Validating a PTAS for triangle-free 2-matching via a simple decomposition theorem,
arXiv:2410.17508, 2024.
- Zhong Huang, Yusuke Kobayashi, Yaping Mao, Bo Ning, and Xiumin Wang:
On the two problems in Ramsey achievement games,
arXiv:2408.01479, 2024.
- Kristóf Bérczi, Tamás Király, Yusuke Kobayashi, Yutaro Yamaguchi, and Yu Yokoi:
Finding spanning trees with perfect matchings,
arXiv:2407.02958, 2024.
- Yusuke Kobayashi and Tatsuya Terao:
Subquadratic submodular maximization with a general matroid constraint,
arXiv:2405.00359, 2024.
- Yuni Iwamasa, Yusuke Kobayashi, and Kenjiro Takazawa:
Finding a maximum restricted t-matching via Boolean edge-CSP,
arXiv:2310.20245, 2023.
- 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.
- Yusuke Kobayashi, Ryoga Mahara, and Souta Sakamoto:
EFX allocations for indivisible chores: matching-based approach,
arXiv:2305.04168, 2023.
- Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto:
Algorithmic theory of qubit routing,
arXiv:2305.02059, 2023.
- 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.
- Yusuke Kobayashi and Takashi Noguchi:
An approximation algorithm for two-edge-connected subgraph problem via triangle-free two-edge-cover,
arXiv:2304.13228, 2023.
- Yusuke Kobayashi, Ryoga Mahara, Tamás Schwarcz:
Reconfiguration of the union of arborescences,
arXiv:2304.13217, 2023.
- 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.
- 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.
- 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.
- Yusuke Kobayashi:
Optimal general factor problem and jump system intersection,
arXiv:2209.00779, 2022.
- 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.
- Yusuke Kobayashi and Ryoga Mahara:
Proportional allocation of indivisible goods up to the least valued good on average,
arXiv:2205.00236, 2022.
- 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.
- 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.
- Asei Inoue and Yusuke Kobayashi:
An additive approximation scheme for the Nash social welfare maximization with identical additive valuations,
arXiv:2201.01419, 2022.
- 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.
- 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.
- Kristóf Bérczi, Naonori Kakimura, and Yusuke Kobayashi:
Market pricing for matroid rank valuations,
arXiv:2007.08759, 2020.
- 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.
- 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.
- 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.
- Yusuke Kobayashi:
Weighted triangle-free 2-matching problem with edge-disjoint forbidden triangles,
arXiv:1911.06436, 2019.
- Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, and Yushi Uno:
Linear-time recognition of double-threshold graphs,
arXiv:1909.09371, 2019.
- Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, and Yusuke Kobayashi:
Parameterized algorithms for maximum cut with connectivity constraints,
arXiv:1908.03389, 2019.
- Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, and Yoshio Okamoto:
Shortest reconfiguration of perfect matchings via alternating cycles,
arXiv:1907.01700, 2019.
- Yoichi Iwata and Yusuke Kobayashi:
Improved analysis of highest-degree branching for feedback vertex set,
arXiv:1905.12233, 2019.
- Satoru Iwata and Yusuke Kobayashi:
A weighted linear matroid parity algorithm,
arXiv:1905.13371, 2019. (Old version: METR 2017-01, University of Tokyo (2017))
- 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.
- 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.
- Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, and Suguru Tamaki:
An FPT algorithm for max-cut parameterized by crossing number,
arXiv:1904.05011, 2019.
- Yusuke Kobayashi:
An FPT algorithm for minimum additive spanner problem,
arXiv:1903.01047, 2019.
- Yasushi Kawase, Yusuke Kobayashi, and Yutaro Yamaguchi:
Tight approximation for unconstrained XOS maximization,
arXiv:1811.09045, 2018.
- Yasushi Kawase, Yusuke Kobayashi, and Yutaro Yamaguchi:
Finding a path in group-labeled graphs with two labels forbidden,
arXiv:1807.00109, 2018.
- Kristóf Bérczi and Yusuke Kobayashi:
The directed disjoint shortest paths problem,
TR-2016-13, Egervary Research Group, Budapest (2016).
- Kristóf Bérczi and Yusuke Kobayashi:
An algorithm for identifying cycle-plus-triangles graphs,
TR-2016-12, Egervary Research Group, Budapest (2016).
- Yusuke Kobayashi and Kenjiro Takazawa:
Randomized strategies for cardinality robustness in the knapsack problem,
RIMS
Preprint, RIMS-1833, 2015.
- 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).
- Yusuke Kobayashi and Sho Toyooka:
Finding a shortest non-zero path in group-labeled graphs,
METR 2015-19, University of Tokyo (2015).
- 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).
- Hiroshi Nishiyama, Yusuke Kobayashi, Yukiko Yamauchi, Shuji Kijima, and Masafumi Yamashita:
The parity Hamiltonian cycle problem,
arXiv:1501.06323, 2015.
- Yusuke Kobayashi:
The complexity of maximizing the difference of two matroid rank functions,
METR 2014-42, University of Tokyo (2014).
- 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).
- 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).
- 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).)
- 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).
- Kota Ishihara and Yusuke Kobayashi:
Routing algorithms under mutual interference constraints,
METR 2013-14, University of Tokyo (2013).
- Yusuke Kobayashi:
Triangle-free 2-matchings and M-concave functions on jump systems,
METR 2013-06, University of Tokyo (2013).
- Yusuke Kobayashi and Yuichi Yoshida:
Algorithms for finding a maximum non-k-linked graph,
METR 2011-23, University of Tokyo (2011).
- Yusuke Kobayashi and Xin Yin:
An algorithm for finding a maximum t-matching excluding complete partite subgraphs,
METR 2011-12, University of Tokyo (2011).
- Ryo Fujita, Yusuke Kobayashi, and Kazuhisa Makino:
Robust matchings and matroid intersections,
METR 2010-20, University of Tokyo (2010).
- 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).
- Yusuke Kobayashi and Christian Sommer:
On shortest disjoint paths in planar graphs,
METR 2009-38, University of Tokyo (2009).
- Yusuke Kobayashi, Kazuo Murota, and Robert Weismantel:
Cone superadditivity of discrete convex functions,
METR 2009-30, University of Tokyo (2009).
- 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).
- Yusuke Kobayashi:
A simple algorithm for finding a maximum triangle-free 2-matching in subcubic graphs,
METR 2009-26, University of Tokyo (2009).
- 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]
- 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.)
- Ken-ichi Kawarabayashi and Yusuke Kobayashi:
Algorithms for finding an induced cycle in planar graphs,
METR 2008-23, University of Tokyo (2008).
- 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.)
- Yusuke Kobayashi:
An extension of the disjoint paths problem,
METR 2007-14, University of Tokyo (2007).
- Yusuke Kobayashi and Kazuo Murota:
Induction of M-convex functions by linking systems,
METR 2006-43, University of Tokyo (2006).
- Yusuke Kobayashi, Kazuo Murota, and Ken'ichiro Tanaka:
Operations on M-convex functions on jump systems,
METR 2006-13, University of Tokyo (2006).
- Naonori Kakimura and Yusuke Kobayashi:
On odd-cycle-symmetry of digraphs,
METR 2005-36, University of Tokyo (2005).
- 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
- [Bachelor's Thesis] グラフの向き付けに関する最適化問題の解法
(An algorithm for minimum cost arc-connectivity orientation),
Faculty of Engineering, University of Tokyo,
March 2005. (in Japanese)
- [Master's Thesis] On a discrete convex function on jump
systems, Department of Mathematical Informatics, Graduate
School of Information Science and Technology, University
of Tokyo, March 2007.
- [Ph.D. Thesis] Algorithms for finding disjoint paths: acceleration and extension,
Department of Mathematical Informatics, Graduate
School of Information Science and Technology, University
of Tokyo, March 2010.
Others (in Japanese)
-
小林佑輔: グラフマイナー理論,
数理科学, No.702 (2021年12月号), サイエンス社,pp. 30--36.
-
小林佑輔: グラフ・ネットワークにおける最適化,
数理科学, No.677 (2019年11月号), サイエンス社,pp. 14--20.
-
山本芳嗣(編著): 基礎数学IV.最適化理論,
東京化学同人.(担当:3.3節,4.1節)
-
小林佑輔: マッチングからマトロイドパリティへ,
電子情報通信学会誌, Vol.101 No.3 (2018年3月), pp. 248--252.
-
小林佑輔,福永拓郎: 通信ネットワークのモデル化と最適化,
オペレーションズ・リサーチ, Vol.60 No.8 (2015年8月号), pp. 443--448.