Publications of Takehiro ITO


Refereed Papers in Journals

  1. Takehiro Ito and Erik D. Demaine,
    Approximability of the Subset Sum Reconfiguration Problem,
    Journal of Combinatorial Optimization, to appear.

  2. Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki and Xiao Zhou,
    On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms,
    Algorithmica, to appear.

  3. Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki and Ryuhei Uehara,
    Route-Enabling Graph Orientation Problems,
    Algorithmica, Vol. 65, Issue 2, pp. 317-338, February 2013.

  4. Takehiro Ito, Takuya Hara, Xiao Zhou and Takao Nishizeki,
    Minimum Cost Partitions of Trees with Supply and Demand,
    Algorithmica, Vol. 64, Issue 3, pp. 400-415, November 2012.

  5. Takehiro Ito, Marcin Kamiński and Erik D. Demaine,
    Reconfiguration of List Edge-Colorings in a Graph,
    Discrete Applied Mathematics, Vol. 160, Issue 15, pp. 2199-2207, October 2012.

  6. Takehiro Ito, Takao Nishizeki, Michael Schröder, Takeaki Uno and Xiao Zhou,
    Partitioning a Weighted Tree into Subtrees with Weights in a Given Range,
    Algorithmica, Vol. 62, Issues 3-4, pp. 823-841, April 2012.

  7. Takehiro Ito, Kazuto Kawamura and Xiao Zhou,
    An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree,
    IEICE Trans. on Information and Systems, Vol. E95-D, No. 3, pp. 737-745, March 2012.

  8. Takehiro Ito, Marcin Kamiński, Daniël Paulusma and Dimitrios M. Thilikos,
    Parameterizing Cut Sets in a Graph by the Number of Their Components,
    Theoretical Computer Science, Vol. 412, Issue 45, pp. 6340-6350, October 2011.

  9. Takehiro Ito, Marcin Kamiński, Daniël Paulusma and Dimitrios M. Thilikos,
    On Disconnected Cuts and Separators,
    Discrete Applied Mathematics, Vol. 159, Issue 13, pp. 1345-1351, August 2011.

  10. Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara and Yushi Uno,
    On the Complexity of Reconfiguration Problems,
    Theoretical Computer Science, Vol. 412, Issues 12-14, pp. 1054-1065, March 2011.

  11. Takehiro Ito, Naoki Sakamoto, Xiao Zhou and Takao Nishizeki,
    Minimum Cost Edge-Colorings of Trees Can be Reduced to Matchings,
    IEICE Trans. on Information and Systems, Vol. E94-D, No. 2, pp. 190-195, February 2011.

  12. Takehiro Ito, Xiao Zhou and Takao Nishizeki,
    Partitioning Graphs of Supply and Demand,
    Discrete Applied Mathematics, Vol. 157, Issue 12, pp. 2620-2633, June 2009.
    (Special issue of Second Workshop on Graph Classes, Optimization, and Width Parameters, 2005)

  13. Takehiro Ito, Erik D. Demaine, Xiao Zhou and Takao Nishizeki,
    Approximability of Partitioning Graphs with Supply and Demand,
    Journal of Discrete Algorithms, Vol. 6, No. 4, pp. 627-650, 2008.

  14. Takehiro Ito, Akira Kato, Xiao Zhou and Takao Nishizeki,
    Algorithms for Finding Distance-Edge-Colorings of Graphs,
    Journal of Discrete Algorithms, Vol. 5, No. 2, pp. 304-322, 2007.

  15. Takehiro Ito, Kazuya Goto, Xiao Zhou and Takao Nishizeki,
    Partitioning a Multi-Weighted Graph to Connected Subgraphs of Almost Uniform Size,
    IEICE Trans. on Information and Systems, Vol. E90-D, No. 2, pp. 449-456, 2007.

  16. Takehiro Ito, Xiao Zhou and Takao Nishizeki,
    Partitioning a Graph of Bounded Tree-Width to Connected Subgraphs of Almost Uniform Size,
    Journal of Discrete Algorithms, Vol. 4, No. 1, pp. 142-154, 2006.

  17. Takehiro Ito, Xiao Zhou and Takao Nishizeki,
    Partitioning Trees of Supply and Demand,
    International Journal of Foundations of Computer Science, Vol. 16, No. 4, pp. 803-827, 2005.
    (This paper received Noguchi Incentive Award.)

  18. Takehiro Ito, Takao Nishizeki and Xiao Zhou,
    Algorithms for Multicolorings of Partial k-Trees,
    IEICE Trans. on Information and Systems, Vol. E86-D, No. 2, pp. 191-200, 2003.
    (This paper received the TELECOM System Technology Award for Student.)



Refereed Papers in International Conferences

  1. Yuichi Asahiro, Hiroshi Eto, Takehiro Ito and Eiji Miyano,
    Complexity of Finding Maximum Regular Induced Subgraphs with Prescribed Degree,
    in Proceedings of the 19th International Symposium on Fundamentals of Computation Theory (FCT 2013),
    Lecture Notes in Computer Science, to appear.

  2. Taku Okada, Akira Suzuki, Takehiro Ito and Xiao Zhou,
    On the Minimum Caterpillar Problem in Digraphs,
    in Proceedings of the 19th Annual International Computing and Combinatorics Conference (COCOON 2013),
    Lecture Notes in Computer Science, to appear.

  3. Kei Uchizawa, Takanori Aoki, Takehiro Ito and Xiao Zhou,
    Generalized Rainbow Connectivity of Graphs,
    in Proceedings of the 7th International Workshop on Algorithms and Computation (WALCOM 2013),
    Lecture Notes in Computer Science, Vol. 7748, pp. 233-244, 2013.

  4. Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara and Takeaki Uno,
    Base Location Problems for Base-Monotone Regions,
    in Proceedings of the 7th International Workshop on Algorithms and Computation (WALCOM 2013),
    Lecture Notes in Computer Science, Vol. 7748, pp. 53-64, 2013.

  5. Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno and Yushi Uno,
    A 4.31-Approximation for the Geometric Unique Coverage Problem on Unit Disks,
    in Proceedings of the 23rd Annual International Symposium on Algorithms and Computation (ISAAC 2012),
    Lecture Notes in Computer Science, Vol. 7676, pp. 372-381, 2012.

  6. Takehiro Ito, Kazuto Kawamura, Hirotaka Ono and Xiao Zhou,
    Reconfiguration of List L(2,1)-Labelings in a Graph,
    in Proceedings of the 23rd Annual International Symposium on Algorithms and Computation (ISAAC 2012),
    Lecture Notes in Computer Science, Vol. 7676, pp. 34-43, 2012.

  7. Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara and Takeaki Uno,
    Algorithms for Computing Optimal Image Segmentation Using Quadtree Decomposition,
    in Proceedings of Thailand-Japan Joint Conference on Computational Geometry and Graphs (TJJCCGG 2012),
    pp. 23-24, 2012.
    (* This paper is on experimental results of the algorithms in our paper in WALCOM 2013.)

  8. Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki and Ryuhei Uehara,
    Packing Trominoes is NP-Complete, #P-Complete and ASP-Complete,
    in Proceedings of the 24th Canadian Conference on Computational Geometry (CCCG 2012),
    pp. 219-224, 2012.

  9. Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno and Yushi Uno,
    A Polynomial-Time Approximation Scheme for the Geometric Unique Coverage Problem on Unit Squares,
    in Proceedings of the 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012),
    Lecture Notes in Computer Science, Vol. 7357, pp. 24-35, 2012.

  10. Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki and Xiao Zhou,
    On the Rainbow Connectivity of Graphs: Complexity and FPT Algorithms,
    in Proceedings of the 17th Annual International Computing and Combinatorics Conference (COCOON 2011),
    Lecture Notes in Computer Science, Vol. 6842, pp. 86-97, 2011.

  11. Takehiro Ito, Kazuto Kawamura and Xiao Zhou,
    An Improved Sufficient Condition for Reconfiguration of List Edge-Colorings in a Tree,
    in Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011),
    Lecture Notes in Computer Science, Vol. 6648, pp. 94-105, 2011.

  12. Takehiro Ito and Erik D. Demaine,
    Approximability of the Subset Sum Reconfiguration Problem,
    in Proceedings of the 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011),
    Lecture Notes in Computer Science, Vol. 6648, pp. 58-69, 2011.

  13. Takehiro Ito, Takuya Hara, Xiao Zhou and Takao Nishizeki,
    Minimum Cost Partitions of Trees with Supply and Demand,
    in Proceedings (Part II) of the 21st Annual International Symposium on Algorithms and Computation (ISAAC 2010),
    Lecture Notes in Computer Science, Vol. 6507, pp. 351-362, 2010.

  14. Takehiro Ito, Naoki Sakamoto, Xiao Zhou and Takao Nishizeki,
    Minimum Cost Edge-Colorings of Trees Can be Reduced to Matchings,
    in Proceedings of the 4th International Frontiers of Algorithmics Workshop (FAW 2010),
    Lecture Notes in Computer Science, Vol. 6213, pp. 274-284, 2010.

  15. Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki and Ryuhei Uehara,
    Route-Enabling Graph Orientation Problems,
    in Proceedings of the 20th Annual International Symposium on Algorithms and Computation (ISAAC 2009),
    Lecture Notes in Computer Science, Vol. 5878, pp. 403-412, 2009.

  16. Takehiro Ito, Marcin Kamiński, Daniël Paulusma and Dimitrios M. Thilikos,
    Parameterizing Cut Sets in a Graph by the Number of Their Components,
    in Proceedings of the 20th Annual International Symposium on Algorithms and Computation (ISAAC 2009),
    Lecture Notes in Computer Science, Vol. 5878, pp. 605-615, 2009.

  17. Takehiro Ito, William S. Kennedy and Bruce A. Reed,
    A Characterization of Graphs with Fractional Total Chromatic Number Equal to Δ+2,
    in Proceedings of the V Latin-American Algorithms, Graphs and Optimization Symposium (LAGOS 2009),
    Electronic Notes in Discrete Mathematics, Vol. 35, pp. 235-240, 2009.

  18. Takehiro Ito, Marcin Kamiński and Erik D. Demaine,
    Reconfiguration of List Edge-Colorings in a Graph,
    in Proceedings of the 11th Algorithms and Data Structures Symposium (WADS 2009),
    Lecture Notes in Computer Science Vol. 5664, pp. 375-386, 2009.

  19. Takehiro Ito, Takeaki Uno, Xiao Zhou and Takao Nishizeki,
    Partitioning a Weighted Tree to Subtrees of Almost Uniform Size,
    in Proceedings of the 19th Annual International Symposium on Algorithms and Computation (ISAAC 2008),
    Lecture Notes in Computer Science Vol. 5369, pp. 196-207, 2008.
    (This paper received the Best Paper Award from ISAAC 2008.)

  20. Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara and Yushi Uno,
    On the Complexity of Reconfiguration Problems,
    in Proceedings of the 19th Annual International Symposium on Algorithms and Computation (ISAAC 2008),
    Lecture Notes in Computer Science Vol. 5369, pp. 28-39, 2008.

  21. Takehiro Ito, Erik D. Demaine, Xiao Zhou and Takao Nishizeki,
    Approximability of Partitioning Graphs with Supply and Demand,
    in Proceedings of the 17th Annual International Symposium on Algorithms and Computation (ISAAC 2006),
    Lecture Notes in Computer Science Vol. 4288, pp. 121-130, 2006.

  22. Takehiro Ito, Kazuya Goto, Xiao Zhou and Takao Nishizeki,
    Partitioning a Multi-weighted Graph to Connected Subgraphs of Almost Uniform Size,
    in Proceedings of the 12th Annual International Computing and Combinatorics Conference (COCOON 2006),
    Lecture Notes in Computer Science Vol. 4112, pp. 63-72, 2006.

  23. Takehiro Ito, Akira Kato, Xiao Zhou and Takao Nishizeki,
    Algorithms for Finding Distance-Edge-Colorings of Graphs,
    in Proceedings of the 11th Annual International Computing and Combinatorics Conference (COCOON 2005),
    Lecture Notes in Computer Science Vol. 3595, pp. 798-807, 2005.

  24. Takehiro Ito, Xiao Zhou and Takao Nishizeki,
    Partitioning Graphs of Supply and Demand,
    in Proceedings of the 2005 IEEE International Symposium on Circuits and Systems (ISCAS 2005),
    pp. 160-163, 2005.

  25. Takehiro Ito, Xiao Zhou and Takao Nishizeki,
    Partitioning a Weighted Graph to Connected Subgraphs of Almost Uniform Size,
    in Proceedings of the 30th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2004),
    Lecture Notes in Computer Science Vol. 3353, pp. 365-376, 2004.

  26. Takehiro Ito, Xiao Zhou and Takao Nishizeki,
    Partitioning Trees of Supply and Demand,
    in Proceedings of the 13th Annual International Symposium on Algorithms and Computation (ISAAC 2002),
    Lecture Notes in Computer Science Vol. 2518, pp. 612-623, 2002.
    (This paper received the Young C&C Author's Prize.)

  27. Takehiro Ito, Takao Nishizeki and Xiao Zhou,
    Algorithms for the Multicolorings of Partial k-Trees,
    in Proceedings of the 8th Annual International Computing and Combinatorics Conference (COCOON 2002),
    Lecture Notes in Computer Science Vol. 2387, pp. 430-439, 2002.



Invited Talk



Other Manuscripts in International Conferences

  1. Taku Okada, Akira Suzuki, Takehiro Ito and Xiao Zhou,
    Algorithm for the Minimum Caterpillar Problem with Terminals,
    in Proceedings of the 6th Annual Meeting of Asian Association for Algorithms and Computation (AAAC 2013),
    p. 25, 2013.

  2. Takehiro Ito,
    Partitioning Graphs of Supply and Demand,
    in Proceedings of Workshop on Algorithms and Computation 2007 (WALCOM 2007),
    pp. 162-179, 2007.

  3. Takehiro Ito, Yoshio Okamoto and Takeshi Tokuyama,
    Algorithms for the Full Steiner Tree Problem,
    in Proceedings of ICALP 2006 Affiliated Workshop "Improving Exponential Time Algorithms," (iETA),
    pp. 39-45, 2006.

  4. Takehiro Ito, Xiao Zhou and Takao Nishizeki,
    Algorithm for Partitioning Graphs of Bounded Tree-Width of Supply and Demand,
    in Proceedings of the 4th Japanese-Hungarian Symposium on Discrete Mathematics and its Applications (JH 2005),
    pp. 114-121, 2005.


Last Updated: June 3, 2013

HOME