Papers by Kenjiro Takazawa

# Papers by Kenjiro Takazawa

### Papers in Submission

1. K. Murota and K. Takazawa:
Relationship of two formulations for shortest bibranchings.
Preprint: arXiv:1706.02029
2. S. Fujishige, T. Király, K. Makino, K. Takazawa and S. Tanigawa:
Minimizing submodular functions on diamonds via generalized fractional matroid matchings.
Preprint: EGRES TR-2014-14

### Papers in Refereed Journals♦ and Refereed Conferences/Symposia/Workshops/Meetings♠

1. M. M. Halldórsson, T. Ishii, K. Makino and K. Takazawa:
Posimodular function optimization.
Proceedings of the 15th International Symposium on Algorithms and Data Structures (WADS 2017), Lecture Notes in Computer Science, 10389, 2017, pp. 437-448. [Acceptance ratio = 45% (49/109)]
2. K. Takazawa:
Excluded $t$-factors in bipartite graphs: A unified framework for nonbipartite matchings and restricted 2-matchings.
Proceedings of the 19th Conference on Integer Programming and Combinatorial Optimization (IPCO 2017), Lecture Notes in Computer Science 10328, 2017, pp. 430-441. [Acceptance ratio = 29% (36/125)]
[Full version: arXiv:1708.00582]

3. K. Takazawa:
Decomposition theorems for square-free 2-matchings in bipartite graphs.
Discrete Applied Mathematics, to appear.
Proceedings of the 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015), Lecture Notes in Computer Science 9224, 2016, pp. 373-387. [Acceptance ratio = 41% (32/79)]
4. K. Takazawa:
Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs.
Discrete Optimization, to appear.
Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016), Leibniz International Proceedings in Informatics 58, 2016, pp. 87:1-87:14. [Acceptance ratio ≤ 38% (84/220)]
5. Y. Kobayashi and K. Takazawa:
Randomized strategies for cardinality robustness in the knapsack problem.
Theoretical Computer Science, to appear.
Proceedings of the 13th Meeting on Analytic Algorithmics and Combinatorics (ANALCO 2016), 2016, pp. 25-33.
6. K. Takazawa:
A 7/6-approximation algorithm for the minimum 2-edge connected subgraph problem in bipartite cubic graphs,
Information Processing Letters, 116 (2016), pp. 550-553.
7. K. Takazawa:
Optimal matching forests and valuated delta-matroids.
SIAM Journal on Discrete Mathematics, 28 (2014), pp. 445-467.
Proceedings of the 15th Conference on Integer Programming and Combinatorial Optimization (IPCO 2011), Lecture Notes in Computer Science 6655, 2011, pp. 404-416. [Acceptance ratio = 30% (33/110)]
8. S. Boyd, S. Iwata and K. Takazawa:
Finding 2-factors closer to TSP tours in cubic graphs.
SIAM Journal on Discrete Mathematics, 27 (2013), pp. 918-939.
9. K. Takazawa:
Shortest bibranchings and valuated matroid intersection.
Japan Journal of Industrial and Applied Mathematics, 29 (2012), pp. 561-573.
10. Y. Kobayashi, J. Szabó and K. Takazawa:
A proof of Cunningham's conjecture on restricted subgraphs and jump systems.
Journal of Combinatorial Theory, Series B, 102 (2012), pp. 948-966.
11. K. Takazawa:
A weighted independent even factor algorithm.
Mathematical Programming, Series A, 132 (2012), pp. 261-276.
12. K. Takazawa:
Even factors: Algorithms and structure.
Combinatorial Optimization and Discrete Algorithms, RIMS Kôkyûroku Bessatsu, B23 (2010), pp. 233-252.
13. K. Takazawa:
A weighted $K_{t,t}$-free $t$-factor algorithm for bipartite graphs.
Mathematics of Operations Research, 34 (2009), pp. 351-362.
Proceedings of the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO 2008), Lecture Notes in Computer Science 5035, 2008, pp. 62-76. [Acceptance ratio = 34% (32/95)]
14. Y. Kobayashi and K. Takazawa:
Even factors, jump systems, and discrete convexity.
Journal of Combinatorial Theory, Series B, 99 (2009), pp. 139-161.
15. S. Iwata and K. Takazawa:
The independent even factor problem.
SIAM Journal on Discrete Mathematics, 22 (2008), pp. 1411-1427.
Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), 2007, pp. 1171-1180. [Acceptance ratio = 36% (139/382)]
16. K. Takazawa:
A weighted even factor algorithm.
Mathematical Programming, Series A, 115 (2008), pp. 223-237.

### Informal Publications

Hungarian-Japanese Symposium
1. K. Takazawa:
Excluded $t$-factors in bipartite graphs: A unified framework for nonbipartite matchings and restricted 2-matchings,
Proceedings of the 10th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2017), 2017,
pp. 483-492.
2. K. Takazawa:
Structure theorems for square-free 2-matchings in bipartite graphs,
Proceedings of the 9th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ 2015), 2015, pp. 69-78.
3. Y. Kobayashi and K. Takazawa:
Square-free 2-matchings in bipartite graphs and jump systems,
Proceedings of the 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2009), 2009, pp. 187-197.
4. K. Takazawa:
A weighted independent even factor algorithm,
Proceedings of the 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (JH 2009), 2009, pp. 361-371.
5. K. Takazawa:
A weighted even factor algorithm,
Proceedings of the 5th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications (HJ 2007), 2007, pp. 43-52.

Technical Reports/Preprints

1. K. Takazawa:
Excluded $t$-factors in bipartite graphs: Unified framework for nonbipartite matchings, restricted 2-matchings, and matroids.
arXiv:1708.00582, 2017.
2. K. Murota and K. Takazawa:
Relationship of two formulations for shortest bibranchings.
arXiv:1706.02029, 2017.
3. K. Takazawa:
Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs,
RIMS Preprint, RIMS-1839, Kyoto University, 2015.
4. Y. Kobayashi and K. Takazawa:
Randomized strategies for cardinality robustness in the knapsack problem,
RIMS Preprint, RIMS-1833, Kyoto University, 2015.
5. K. Takazawa:
Approximation algorithms for the minimum 2-edge connected spanning subgraph problem and the graph-TSP in regular bipartite graphs via restricted 2-factors,
RIMS Preprint, RIMS-1826, Kyoto University, 2015.
6. K. Takazawa:
Decomposition theorems for square-free 2-matchings in bipartite graphs,
RIMS Preprint, RIMS-1813, Kyoto University, 2015.
7. S. Fujishige, T. Király, K. Makino, K. Takazawa and S. Tanigawa:
Minimizing submodular functions on diamonds via generalized fractional matroid matchings,
EGRES Technical Reports, TR-2014-14, Egerváry Research Group, 2014.
8. S. Boyd, S. Iwata and K. Takazawa:
Covering cuts in bridgeless cubic graphs,
RIMS Preprint, RIMS-1731, Kyoto University, 2011.
9. K. Takazawa:
Optimal matching forests and valuated delta-matroids.
RIMS Preprint, RIMS-1718, Kyoto University, 2011.
10. Y. Kobayashi, J. Szabó and K. Takazawa:
A proof to Cunningham's conjecture on restricted subgraphs and jump systems,
EGRES Technical Reports, TR-2010-04, Egerváry Research Group, 2010.
11. K. Takazawa:
A weighted independent even factor algorithm,
Mathematical Engineering Technical Reports, METR 2009-15, University of Tokyo, 2009.
12. Y. Kobayashi and K. Takazawa:
Square-free 2-matchings in bipartite graphs and jump systems,
Mathematical Engineering Technical Reports, METR 2008-40, University of Tokyo, 2008.
13. K. Takazawa:
A weighted $K_{t,t}$-free $t$-factor algorithm for bipartite graphs,
Mathematical Engineering Technical Reports, METR 2008-07, University of Tokyo, 2008.
14. Y. Kobayashi and K. Takazawa:
Even factors, jump systems, and discrete convexity,
Mathematical Engineering Technical Reports, METR 2007-36, University of Tokyo, 2007.
15. S. Iwata and K. Takazawa:
The independent even factor problem,
Mathematical Engineering Technical Reports, METR 2006-24, University of Tokyo, 2006.
16. K. Takazawa:
A weighted even factor algorithm,
Mathematical Engineering Technical Reports, METR 2005-17, University of Tokyo, 2005.

## Theses

• [Ph.D. Thesis] Combinatorial Algorithms for Generalized Matching Problems, University of Tokyo, 2010 (supervised by Kazuo Murota).

• [Master's Thesis] A Unified Approach to Combinatorial Algorithms for Matchings and Matroids, University of Tokyo, 2007 (supervised by Kazuo Murota and Satoru Iwata).