Papers by Kenjiro Takazawa
Papers in Submission/Preparation

K. Takazawa:
The $b$bibranching problem: TDI system, packing, and discrete convexity.
Preprint: arXiv:1802.03235
 S. Fujishige, T. Király, K. Makino, K. Takazawa and S. Tanigawa:
Minimizing submodular functions on diamonds via generalized fractional matroid matchings.
Preprint: EGRES TR201414
Papers in Refereed Journals^{♦} and Refereed Conferences^{♠}

K. Murota and K. Takazawa:
Relationship of two formulations for shortest bibranchings.
♦ Japan Journal of Industrial and Applied Mathematics, to appear.
 N. Kakimura, N. Kamiyama and K. Takazawa:
The $b$branching problem in digraphs.
♦ Discrete Applied Mathematics, 283 (2020), 565576.
♠
Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018),
Leibniz International Proceedings in Informatics 117, 2018, pp. 12:112:15.
[Acceptance ratio ≤ 40% (84/210)]
 M. Kawasaki and K. Takazawa:
Improving approximation ratios for the clustered traveling salesman problem.
♦ Journal of the Operations Research Society of Japan,
63 (2020), 6070.

S. Fujishige, K. Takazawa and Y. Yokoi:
A note on a nearly uniform partition into common independent sets of two matroids.
♦ Journal of the Operations Research Society of Japan, 63 (2020), 7177.

K. Takazawa:
Notes on equitable partitions into matching forests in mixed graphs and into $b$branchings in digraphs.
♠
Proceedings of the 6th International Symposium on Combinatorial Optimization (ISCO 2020),
Lecture Notes in Computer Science,
12176, pp. 214224.
[Acceptance ratio = 38% (25/66)]

Y. Iwamasa and K. Takazawa:
Optimal matroid bases with intersection constraints: Valuated matroids, Mconvex functions, and their applications.
♠
Proceedings of the 16th Annual Conference on Theory and Applications of Models of Computation (TAMC 2020),
Lecture Notes in Computer Science, 12337, pp. 156167.
[Acceptance ratio = 45% (37/83)]

K. Takazawa and Y. Yokoi:
A generalizedpolymatroid approach to disjoint common independent sets in two matroids.
♦ Discrete Mathematics, 342 (2019), 20022011.

K. Takazawa:
Generalizations of weighted matroid congestion games: Pure Nash equilibrium, sensitivity analysis, and discrete convex function.
♦ Journal of Combinatorial Optimization, 38 (2019), 10431065.
♠
Proceedings of the 15th Annual Conference on Theory and Applications of Models of Computation (TAMC 2019),
Lecture Notes in Computer Science, 11436, pp. 594614.
 K. Takazawa:
Decomposition theorems for squarefree 2matchings in bipartite graphs.
♦ Discrete Applied Mathematics, 233 (2017), pp. 215223.
♠ Proceedings of
the 41st International Workshop on GraphTheoretic Concepts in Computer Science (WG 2015),
Lecture Notes in Computer Science 9224, 2016, pp. 373387. [Acceptance ratio = 41% (32/79)]
 K. Takazawa:
Finding a maximum 2matching excluding prescribed cycles in bipartite graphs.
♦ Discrete Optimization, 26 (2017), pp. 2640.
♠ Proceedings of
the 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016),
Leibniz International Proceedings in Informatics 58, 2016, pp. 87:187:14. [Acceptance ratio ≤ 38% (84/220)]
 Y. Kobayashi and K. Takazawa:
Randomized strategies for cardinality robustness in the knapsack problem.
♦ Theoretical Computer Science, 699 (2017), pp. 5362.
♠ Proceedings of
the 13th Meeting on Analytic Algorithmics and Combinatorics (ANALCO 2016),
2016, pp. 2533.
 K. Takazawa:
Excluded $t$factors in bipartite graphs:
A unified framework for nonbipartite matchings and restricted 2matchings.
♠ Proceedings of
the 19th Conference on Integer Programming and Combinatorial Optimization (IPCO 2017),
Lecture Notes in Computer Science 10328, 2017, pp. 430441.
[Acceptance ratio = 29% (36/125)]
[Full version: arXiv:1708.00582]

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. 437448.
[Acceptance ratio = 45% (49/109)]
 K. Takazawa:
A 7/6approximation algorithm for the minimum 2edge connected subgraph problem in bipartite cubic graphs.
♦ Information Processing Letters, 116 (2016), pp. 550553.
 K. Takazawa:
Optimal matching forests and valuated deltamatroids.
♦ SIAM Journal on Discrete Mathematics, 28 (2014), pp. 445467.
♠ Proceedings of
the 15th Conference on Integer Programming and Combinatorial Optimization (IPCO 2011),
Lecture Notes in Computer Science 6655, 2011, pp. 404416.
[Acceptance ratio = 30% (33/110)]
 S. Boyd, S. Iwata and K. Takazawa:
Finding 2factors closer to TSP tours in cubic graphs.
♦ SIAM Journal on Discrete Mathematics, 27 (2013), pp. 918939.
 K. Takazawa:
Shortest bibranchings and valuated matroid intersection.
♦ Japan Journal of Industrial and Applied Mathematics, 29 (2012), pp. 561573.
 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. 948966.
 K. Takazawa:
A weighted independent even factor algorithm.
♦ Mathematical Programming, Series A, 132 (2012), pp. 261276.

K. Takazawa:
Even factors: Algorithms and structure.
♦
Combinatorial Optimization and Discrete Algorithms,
RIMS Kôkyûroku Bessatsu,
B23 (2010), pp. 233252.
 Y. Kobayashi and K. Takazawa:
Even factors, jump systems, and discrete convexity.
♦ Journal of Combinatorial Theory, Series B, 99 (2009), pp. 139161.
 K. Takazawa:
A weighted $K_{t,t}$free $t$factor algorithm for bipartite graphs.
♦ Mathematics of Operations Research, 34 (2009), pp. 351362.
♠
Proceedings of
the 13th Conference on Integer Programming and Combinatorial Optimization (IPCO 2008),
Lecture Notes in Computer Science 5035, 2008, pp. 6276.
[Acceptance ratio = 34% (32/95)]
 K. Takazawa:
A weighted even factor algorithm.
♦ Mathematical Programming, Series A, 115 (2008), pp. 223237.
 S. Iwata and K. Takazawa:
The independent even factor problem.
♦ SIAM Journal on Discrete Mathematics, 22 (2008), pp. 14111427.
♠ Proceedings of
the 18th ACMSIAM Symposium on Discrete Algorithms (SODA 2007),
2007, pp. 11711180. [Acceptance ratio = 36% (139/382)]
Informal Publications
HungarianJapanese Symposium
 K. Takazawa:
$b$branchings in digraphs: Branchings with higher indegree.
Proceedings of
the 11th JapaneseHungarian Symposium on Discrete Mathematics and Its Applications (HJ 2019),
2019, pp. 7988.
 K. Takazawa:
Excluded $t$factors in bipartite graphs:
A unified framework for nonbipartite matchings and restricted 2matchings.
Proceedings of
the 10th JapaneseHungarian Symposium on Discrete Mathematics and Its Applications (JH 2017),
2017,
pp. 483492.
 K. Takazawa:
Structure theorems for squarefree 2matchings in bipartite graphs.
Proceedings of
the 9th HungarianJapanese Symposium on Discrete Mathematics and Its Applications (HJ 2015),
2015, pp. 6978.
 Y. Kobayashi and K. Takazawa:
Squarefree 2matchings in bipartite graphs and jump systems.
Proceedings of
the 6th JapaneseHungarian Symposium on Discrete Mathematics and Its Applications (JH 2009),
2009, pp. 187197.
 K. Takazawa:
A weighted independent even factor algorithm.
Proceedings of
the 6th JapaneseHungarian Symposium on Discrete Mathematics and Its Applications (JH 2009),
2009, pp. 361371.
 K. Takazawa:
A weighted even factor algorithm.
Proceedings of
the 5th HungarianJapanese Symposium on Discrete Mathematics and Its Applications (HJ 2007),
2007, pp. 4352.
Technical Reports/Preprints

K. Takazawa:
Notes on equitable partitions into matching forests in mixed graphs and into $b$branchings in digraphs.
arXiv:2003.10774, 2020.

Y. Iwamasa and K. Takazawa:
Optimal matroid bases with intersection constraints: Valuated matroids, Mconvex functions, and their applications.
arXiv:2003.02424, 2020.

S. Fujishige, K. Takazawa and Yu Yokoi:
A note on a nearly uniform partition into common independent sets of two matroids.
arXiv:1909.13261, 2019.

K. Takazawa:
Mconvexity of the minimumcost packings of arborescences.
arXiv:1805.08381, 2018.

K. Takazawa and Y. Yokoi:
A generalizedpolymatroid approach to disjoint common independent sets in two matroids.
arXiv:1805.05528, 2018.

K. Takazawa:
The $b$bibranching problem: TDI system, packing, and discrete convexity.
arXiv:1802.03235, 2018.

N. Kakimura, N. Kamiyama and K. Takazawa:
The $b$branching problem in digraphs.
arXiv:1802.02381, 2018.

K. Takazawa:
Excluded $t$factors in bipartite graphs: Unified framework for nonbipartite matchings, restricted 2matchings, and matroids.
arXiv:1708.00582, 2017.

K. Murota and K. Takazawa:
Relationship of two formulations for shortest bibranchings.
arXiv:1706.02029, 2017.
 K. Takazawa:
Finding a maximum 2matching excluding prescribed cycles in bipartite graphs.
RIMS Preprint,
RIMS1839, Kyoto University, 2015.
 Y. Kobayashi and K. Takazawa:
Randomized strategies for cardinality robustness in the knapsack problem.
RIMS Preprint,
RIMS1833, Kyoto University, 2015.
 K. Takazawa:
Approximation algorithms for the minimum 2edge connected spanning subgraph problem and
the graphTSP in regular bipartite graphs via restricted 2factors.
RIMS Preprint,
RIMS1826, Kyoto University, 2015.
 K. Takazawa:
Decomposition theorems for squarefree 2matchings in bipartite graphs.
RIMS Preprint,
RIMS1813, Kyoto University, 2015.
 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, TR201414, Egerváry Research Group, 2014.
(See also RIMS Preprint,
RIMS1812, Kyoto University, 2015.)
 S. Boyd, S. Iwata and K. Takazawa:
Covering cuts in bridgeless cubic graphs.
RIMS Preprint,
RIMS1731, Kyoto University, 2011.
 K. Takazawa:
Optimal matching forests and valuated deltamatroids.
RIMS Preprint,
RIMS1718, Kyoto University, 2011.
 Y. Kobayashi, J. Szabó and K. Takazawa:
A proof to Cunningham's conjecture on restricted subgraphs and jump systems.
EGRES Technical Reports, TR201004, Egerváry Research Group, 2010.
 K. Takazawa:
A weighted independent even factor algorithm.
Mathematical Engineering Technical Reports, METR 200915, University of Tokyo, 2009.
 Y. Kobayashi and K. Takazawa:
Squarefree 2matchings in bipartite graphs and jump systems.
Mathematical Engineering Technical Reports, METR 200840, University of Tokyo, 2008.
(See also RIMS Preprint,
RIMS1640, Kyoto University, 2008.)
 K. Takazawa:
A weighted $K_{t,t}$free
$t$factor algorithm for bipartite graphs.
Mathematical Engineering Technical Reports, METR 200807, University of Tokyo, 2008.
(See also RIMS Preprint,
RIMS1621, Kyoto University, 2008.)
 Y. Kobayashi and K. Takazawa:
Even factors, jump systems, and discrete convexity.
Mathematical Engineering Technical Reports, METR 200736, University of Tokyo, 2007.
(See also RIMS Preprint,
RIMS1595, Kyoto University, 2007.)
 S. Iwata and K. Takazawa:
The independent even factor problem.
Mathematical Engineering Technical Reports, METR 200624, University of Tokyo, 2006.
 K. Takazawa:
A weighted even factor algorithm.
Mathematical Engineering Technical Reports, METR 200517, 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).
