Papers by Kenjiro Takazawa

Papers by Kenjiro Takazawa

Papers in Submission/Preparation

  1. K. Takazawa: The $b$-bibranching problem: TDI system, packing, and discrete convexity. Preprint: arXiv:1802.03235
  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

  1. K. Murota and K. Takazawa: Relationship of two formulations for shortest bibranchings.
    Japan Journal of Industrial and Applied Mathematics, to appear.
  2. N. Kakimura, N. Kamiyama and K. Takazawa: The $b$-branching problem in digraphs.
    Discrete Applied Mathematics, 283 (2020), 565-576.
    Proceedings of the 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Leibniz International Proceedings in Informatics 117, 2018, pp. 12:1-12:15. [Acceptance ratio ≤ 40% (84/210)]

  3. M. Kawasaki and K. Takazawa: Improving approximation ratios for the clustered traveling salesman problem.
    Journal of the Operations Research Society of Japan, 63 (2020), 60-70.
  4. 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), 71-77.
  5. 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. 214-224. [Acceptance ratio = 38%]
  6. Y. Iwamasa and K. Takazawa: Optimal matroid bases with intersection constraints: Valuated matroids, M-convex 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. 156-167.
  7. K. Takazawa and Y. Yokoi: A generalized-polymatroid approach to disjoint common independent sets in two matroids.
    Discrete Mathematics, 342 (2019), 2002-2011.
  8. K. Takazawa: Generalizations of weighted matroid congestion games: Pure Nash equilibrium, sensitivity analysis, and discrete convex function.
    Journal of Combinatorial Optimization, 38 (2019), 1043-1065.
    Proceedings of the 15th Annual Conference on Theory and Applications of Models of Computation (TAMC 2019), Lecture Notes in Computer Science, 11436, pp. 594-614.
  9. K. Takazawa: Decomposition theorems for square-free 2-matchings in bipartite graphs.
    Discrete Applied Mathematics, 233 (2017), pp. 215-223.
    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)]
  10. K. Takazawa: Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs.
    Discrete Optimization, 26 (2017), pp. 26-40.
    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)]
  11. Y. Kobayashi and K. Takazawa: Randomized strategies for cardinality robustness in the knapsack problem.
    Theoretical Computer Science, 699 (2017), pp. 53-62.
    Proceedings of the 13th Meeting on Analytic Algorithmics and Combinatorics (ANALCO 2016), 2016, pp. 25-33.
  12. 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]

  13. 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)]
  14. 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.
  15. 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)]
  16. 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.
  17. K. Takazawa: Shortest bibranchings and valuated matroid intersection.
    Japan Journal of Industrial and Applied Mathematics, 29 (2012), pp. 561-573.
  18. 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.
  19. K. Takazawa: A weighted independent even factor algorithm.
    Mathematical Programming, Series A, 132 (2012), pp. 261-276.
  20. K. Takazawa: Even factors: Algorithms and structure.
    Combinatorial Optimization and Discrete Algorithms, RIMS Kôkyûroku Bessatsu, B23 (2010), pp. 233-252.
  21. Y. Kobayashi and K. Takazawa: Even factors, jump systems, and discrete convexity.
    Journal of Combinatorial Theory, Series B, 99 (2009), pp. 139-161.
  22. 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)]
  23. K. Takazawa: A weighted even factor algorithm.
    Mathematical Programming, Series A, 115 (2008), pp. 223-237.
  24. 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)]

Informal Publications

Hungarian-Japanese Symposium
  1. K. Takazawa: $b$-branchings in digraphs: Branchings with higher indegree. Proceedings of the 11th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications (HJ 2019), 2019, pp. 79-88.
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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: Notes on equitable partitions into matching forests in mixed graphs and into $b$-branchings in digraphs. arXiv:2003.10774, 2020.
  2. Y. Iwamasa and K. Takazawa: Optimal matroid bases with intersection constraints: Valuated matroids, M-convex functions, and their applications. arXiv:2003.02424, 2020.
  3. 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.
  4. K. Takazawa: M-convexity of the minimum-cost packings of arborescences. arXiv:1805.08381, 2018.
  5. K. Takazawa and Y. Yokoi: A generalized-polymatroid approach to disjoint common independent sets in two matroids. arXiv:1805.05528, 2018.

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

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

  8. K. Takazawa: Excluded $t$-factors in bipartite graphs: Unified framework for nonbipartite matchings, restricted 2-matchings, and matroids. arXiv:1708.00582, 2017.
  9. K. Murota and K. Takazawa: Relationship of two formulations for shortest bibranchings. arXiv:1706.02029, 2017.
  10. K. Takazawa: Finding a maximum 2-matching excluding prescribed cycles in bipartite graphs. RIMS Preprint, RIMS-1839, Kyoto University, 2015.
  11. Y. Kobayashi and K. Takazawa: Randomized strategies for cardinality robustness in the knapsack problem. RIMS Preprint, RIMS-1833, Kyoto University, 2015.
  12. 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.
  13. K. Takazawa: Decomposition theorems for square-free 2-matchings in bipartite graphs. RIMS Preprint, RIMS-1813, Kyoto University, 2015.
  14. 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. (See also RIMS Preprint, RIMS-1812, Kyoto University, 2015.)
  15. S. Boyd, S. Iwata and K. Takazawa: Covering cuts in bridgeless cubic graphs. RIMS Preprint, RIMS-1731, Kyoto University, 2011.
  16. K. Takazawa: Optimal matching forests and valuated delta-matroids. RIMS Preprint, RIMS-1718, Kyoto University, 2011.
  17. 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.
  18. K. Takazawa: A weighted independent even factor algorithm. Mathematical Engineering Technical Reports, METR 2009-15, University of Tokyo, 2009.
  19. 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. (See also RIMS Preprint, RIMS-1640, Kyoto University, 2008.)
  20. 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. (See also RIMS Preprint, RIMS-1621, Kyoto University, 2008.)
  21. Y. Kobayashi and K. Takazawa: Even factors, jump systems, and discrete convexity. Mathematical Engineering Technical Reports, METR 2007-36, University of Tokyo, 2007. (See also RIMS Preprint, RIMS-1595, Kyoto University, 2007.)
  22. S. Iwata and K. Takazawa: The independent even factor problem. Mathematical Engineering Technical Reports, METR 2006-24, University of Tokyo, 2006.
  23. 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).

Return to Takazawa's Home