伊藤 健洋

研究成果

年別の研究成果 2002 2012 2014 2015 2017 2019 2020 2022 2023

• 65 Conference contribution
• 59 Article
• 3 Chapter
• 2 Paper
• 3 その他
  • 2 Conference article
  • 1 Editorial

年別の研究成果

年別の研究成果

検索結果

• 2023

  Reconfiguring (non-spanning) arborescences

  Ito, T., Iwamasa, Y., Kobayashi, Y., Nakahata, Y., Otachi, Y. & Wasa, K., 2023 1月 17, In: Theoretical Computer Science. 943, p. 131-141 11 p.

  研究成果: Article › 査読

  • Sequences 100%
  • Directed Graphs 75%
  • Reconfiguration 75%
  • Polynomial Time 25%
  • Polynomial Time Algorithm 25%
• 2022

  A parameterized view to the robust recoverable base problem of matroids under structural uncertainty

  Ito, T., Kakimura, N., Kamiyama, N., Kobayashi, Y. & Okamoto, Y., 2022 5月, In: Operations Research Letters. 50, 3, p. 370-375 6 p.

  研究成果: Article › 査読

  Open Access

  • Bases 100%
  • Combinatorial Structure 50%
  • Weights 50%
  • Number 50%
  • Parameters 50%

• Approximability of the Distance Independent Set Problem on Regular Graphs and Planar Graphs

  Eto, H., Ito, T., Liu, Z. & Miyano, E., 2022 9月, In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. 105, 9, p. 1211-1222 12 p.

  研究成果: Article › 査読

  • Independent Set 100%
  • Approximation 100%
  • Regular Graph 80%
  • Polynomial Time 60%
  • Planar Graph 60%

• Happy Set Problem on Subclasses of Co-comparability Graphs

  Eto, H., Ito, T., Miyano, E., Suzuki, A. & Tamura, Y., 2022, (Accepted/In press) In: Algorithmica.

  研究成果: Article › 査読

  • Vertex 100%
  • Comparability Graph 66%
  • Graph 66%
  • Running Time 33%
  • Interval Graph 33%

• Incremental optimization of independent sets under the reconfiguration framework

  Ito, T., Mizuta, H., Nishimura, N. & Suzuki, A., 2022 7月, In: Journal of Combinatorial Optimization. 43, 5, p. 1264-1279 16 p.

  研究成果: Article › 査読

  • Independent Set 100%
  • Graph 83%
  • Parameters 83%
  • Planar Graph 33%
  • Algorithm 33%
  4 被引用数 (Scopus)

• SHORTEST RECONFIGURATION of PERFECT MATCHINGS VIA ALTERNATING CYCLES^∗

  Takehiro, I. T. O., Kakimura, N., Kamiyama, N., Kobayashi, Y. & Okamoto, Y., 2022, In: SIAM Journal on Discrete Mathematics. 36, 2, p. 1102-1123 22 p.

  研究成果: Article › 査読

  • Perfect Matchings 100%
  • Cycles 37%
  • Polytope 25%
  • Graph 25%
  • Polynomial Time 12%
  1 被引用数 (Scopus)
• 2021

  Algorithms for gerrymandering over graphs

  Ito, T., Kamiyama, N., Kobayashi, Y. & Okamoto, Y., 2021 5月 8, In: Theoretical Computer Science. 868, p. 30-45 16 p.

  研究成果: Article › 査読

  • Polynomial Time 100%
  • Graph 100%
  • Number 100%
  • Complete 100%
  • Polynomial Time Algorithm 100%
  4 被引用数 (Scopus)

• Approximability of the independent feedback vertex set problem for bipartite graphs

  Tamura, Y., Ito, T. & Zhou, X., 2021 1月 6, In: Theoretical Computer Science. 849, p. 227-236 10 p.

  研究成果: Article › 査読

  • Vertex 100%
  • Approximation Algorithms 37%
  • Polynomial Time 25%
  • Planar Graph 25%
  • Independent Set 12%
  1 被引用数 (Scopus)
• 2020

  A cell model in the ventral visual pathway for the detection of circles of curvature constituting figures

  Kawakami, S., Ito, T., Makino, Y., Hashimoto, M. & Yano, M., 2020 11月, In: Heliyon. 6, 11, e05397.

  研究成果: Article › 査読

  Open Access

  • Circle 100%
  • Detection 75%
  • Simple Cell 20%
  • Cell Model 20%
  • Transforms 15%

• Complexity of the multi-service center problem

  Ito, T., Kakimura, N. & Kobayashi, Y., 2020 11月 24, In: Theoretical Computer Science. 842, p. 18-27 10 p.

  研究成果: Article › 査読

  Open Access

  • Vertex 100%
  • Service 50%
  • Graph 33%
  • Complexity 33%
  • Polynomial Time 16%
  1 被引用数 (Scopus)

• Diameter of colorings under Kempe changes

  Bonamy, M., Heinrich, M., Ito, T., Kobayashi, Y., Mizuta, H., Mühlenthaler, M., Suzuki, A. & Wasa, K., 2020 10月 24, In: Theoretical Computer Science. 838, p. 45-57 13 p.

  研究成果: Article › 査読

  • Coloring 100%
  • Graph 57%
  • Classes 42%
  • Complete 28%
  • Polynomial Time Algorithm 14%
  4 被引用数 (Scopus)

• Parameterized complexity of independent set reconfiguration problems

  Ito, T., Kamiński, M., Ono, H., Suzuki, A., Uehara, R. & Yamanaka, K., 2020 9月 15, In: Discrete Applied Mathematics. 283, p. 336-345 10 p.

  研究成果: Article › 査読

  • Independent Set 100%
  • Sequences 57%
  • Number 42%
  • Algorithm 28%
  • Vertex 28%
  6 被引用数 (Scopus)

• Reconfiguring spanning and induced subgraphs

  Hanaka, T., Ito, T., Mizuta, H., Moore, B., Nishimura, N., Subramanya, V., Suzuki, A. & Vaidyanathan, K., 2020 2月 2, In: Theoretical Computer Science. 806, p. 553-566 14 p.

  研究成果: Article › 査読

  • Subgraphs 100%
  • Independent Set 50%
  • Feasible Solution 50%
  • Solution Space 50%
  • Complexity 50%
  4 被引用数 (Scopus)
• 2019

  Minimum-Cost b-Edge Dominating Sets on Trees

  Ito, T., Kakimura, N., Kamiyama, N., Kobayashi, Y. & Okamoto, Y., 2019 1月 15, In: Algorithmica. 81, 1, p. 343-366 24 p.

  研究成果: Article › 査読

  • Trees 100%
  • Dominating Set 37%
  • Edge 37%
  • Polynomial Time Algorithm 37%
  • Open Problem 25%
  2 被引用数 (Scopus)

• Reconfiguration of colorable sets in classes of perfect graphs

  Ito, T. & Otachi, Y., 2019 6月 7, In: Theoretical Computer Science. 772, p. 111-122 12 p.

  研究成果: Article › 査読

  Open Access

  • Graph 100%
  • Interval Graph 57%
  • Reconfiguration 57%
  • Chordal Graph 42%
  • Polynomial Time 28%
  4 被引用数 (Scopus)

• Reconfiguration of maximum-weight b-matchings in a graph

  Ito, T., Kakimura, N., Kamiyama, N., Kobayashi, Y. & Okamoto, Y., 2019 2月 15, In: Journal of Combinatorial Optimization. 37, 2, p. 454-464 11 p.

  研究成果: Article › 査読

  • Polynomial Time 100%
  • Reconfiguration 100%
  • Reconfiguration Problem 100%
  • Bipartite Graph 100%
  • Positive Integer 50%
  2 被引用数 (Scopus)

• The coloring reconfiguration problem on specific graph classes

  Hatanaka, T., Ito, T. & Zhou, X., 2019 3月 1, In: IEICE Transactions on Information and Systems. E102D, 3, p. 423-429 7 p.

  研究成果: Article › 査読

  Open Access

  • Graph 100%
  • Classes 75%
  • Constant 50%
  • Complete 50%
  • Vertex 50%
  4 被引用数 (Scopus)
• 2018

  Parameterized complexity of the list coloring reconfiguration problem with graph parameters

  Hatanaka, T., Ito, T. & Zhou, X., 2018 8月 29, In: Theoretical Computer Science. 739, p. 65-79 15 p.

  研究成果: Article › 査読

  Open Access

  • Parameters 100%
  • Graph 85%
  • Vertex 57%
  • Coloring 42%
  • Algorithm 28%
  3 被引用数 (Scopus)

• The complexity of (List) edge-coloring reconfiguration problem

  Osawa, H., Suzuki, A., Ito, T. & Zhou, X., 2018 1月, In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. E101A, 1, p. 232-238 7 p.

  研究成果: Article › 査読

  • Coloring 100%
  • Planar Graph 75%
  • Complexity 50%
  • Polynomial Time 25%
  • Reconfiguration Problem 25%
  1 被引用数 (Scopus)
• 2017

  Complexity of Tiling a Polygon with Trominoes or Bars

  Horiyama, T., Ito, T., Nakatsuka, K., Suzuki, A. & Uehara, R., 2017 10月 1, In: Discrete and Computational Geometry. 58, 3, p. 686-704 19 p.

  研究成果: Article › 査読

  • Polygon 100%
  • Completeness 50%
  • Unit Square 50%
  • Computational 25%
  • Open Question 25%
  9 被引用数 (Scopus)

• Efficient stabilization of cooperative matching games

  Ito, T., Kakimura, N., Kamiyama, N., Kobayashi, Y. & Okamoto, Y., 2017 5月 16, In: Theoretical Computer Science. 677, p. 69-82 14 p.

  研究成果: Article › 査読

  • Networks 100%
  • Polynomial Time 33%
  • Classification 33%
  • Combinatorial Optimization Problem 33%
  • Networking Environment 33%
  10 被引用数 (Scopus)

• Reconfiguration of steiner trees in an unweighted graph

  Mizuta, H., Ito, T. & Zhou, X., 2017 7月, In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. E100A, 7, p. 1532-1540 9 p.

  研究成果: Article › 査読

  • Trees 100%
  • Graph 75%
  • Linear Time 25%
  • Interval Graph 25%
  • Edge 25%
  4 被引用数 (Scopus)
• 2016

  A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares

  Ito, T., Nakano, S. I., Okamoto, Y., Otachi, Y., Uehara, R., Uno, T. & Uno, Y., 2016 1月, In: Computational Geometry: Theory and Applications. 51, p. 25-39 15 p.

  研究成果: Article › 査読

  • Unit Square 100%
  • Points 100%
  • Polynomial Time 50%
  • Approximation 50%
  • Total Cost 25%
  9 被引用数 (Scopus)

• Reconfiguration of vertex covers in a graph

  Ito, T., Nooka, H. & Zhou, X., 2016 3月, In: IEICE Transactions on Information and Systems. E99D, 3, p. 598-606 9 p.

  研究成果: Article › 査読

  • Vertex 100%
  • Graph 83%
  • Sequences 50%
  • Upper Bound 33%
  • Linear Time 16%
  20 被引用数 (Scopus)

• The complexity of dominating set reconfiguration

  Haddadan, A., Ito, T., Mouawad, A. E., Nishimura, N., Ono, H., Suzuki, A. & Tebbal, Y., 2016 10月 25, In: Theoretical Computer Science. 651, p. 37-49 13 p.

  研究成果: Article › 査読

  • Graph 100%
  • Dominating Set 80%
  • Sequences 60%
  • Linear Time 40%
  • Number 40%
  26 被引用数 (Scopus)

• The minimum vulnerability problem on specific graph classes

  Aoki, Y., Halldórsson, B. V., Halldórsson, M. M., Ito, T., Konrad, C. & Zhou, X., 2016 11月 1, In: Journal of Combinatorial Optimization. 32, 4, p. 1288-1304 17 p.

  研究成果: Article › 査読

  • Edge 100%
  • Graph 50%
  • Classes 50%
  • Directed Graphs 50%
  • Vulnerabilities 50%
  3 被引用数 (Scopus)
• 2015

  Algorithms for the independent feedback vertex set problem

  Tamura, Y., Ito, T. & Zhou, X., 2015 6月 1, In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. E98A, 6, p. 1179-1188 10 p.

  研究成果: Article › 査読

  • Vertex 100%
  • Algorithm 80%
  • Graph 80%
  • Parameters 40%
  • Bipartite Graph 40%
  9 被引用数 (Scopus)

• Linear-time algorithm for sliding tokens on trees

  Demaine, E. D., Demaine, M. L., Fox-Epstein, E., Hoang, D. A., Ito, T., Ono, H., Otachi, Y., Uehara, R. & Yamada, T., 2015 10月 4, In: Theoretical Computer Science. 600, p. 132-142 11 p.

  研究成果: Article › 査読

  Open Access

  • Independent Set 100%
  • Sequences 100%
  • Linear Time 50%
  • Trees 50%
  • Graph 50%
  41 被引用数 (Scopus)

• Swapping labeled tokens on graphs

  Yamanaka, K., Demaine, E. D., Ito, T., Kawahara, J., Kiyomi, M., Okamoto, Y., Saitoh, T., Suzuki, A., Uchizawa, K. & Uno, T., 2015 6月 27, In: Theoretical Computer Science. 586, p. 81-94 14 p.

  研究成果: Article › 査読

  • Polynomial Time 100%
  • Graph 75%
  • Trees 50%
  • Vertex 50%
  • Approximation Algorithms 50%
  43 被引用数 (Scopus)

• The list coloring reconfiguration problem for bounded pathwidth graphs

  Hatanaka, T., Ito, T. & Zhou, X., 2015 6月 1, In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. E98A, 6, p. 1168-1178 11 p.

  研究成果: Article › 査読

  • Coloring 100%
  • Planar Graph 50%
  • Polynomial Time Algorithm 25%
  • Reconfiguration Problem 25%
  • Subclasses 25%
  17 被引用数 (Scopus)
• 2014

  A 4.31-approximation for the geometric unique coverage problem on unit disks

  Ito, T., Nakano, S. I., Okamoto, Y., Otachi, Y., Uehara, R., Uno, T. & Uno, Y., 2014, In: Theoretical Computer Science. 544, C, p. 14-31 18 p.

  研究成果: Article › 査読

  • Unit Disk 100%
  • Points 100%
  • Algorithm 100%
  • Approximation 100%
  • Polynomial Time 50%
  12 被引用数 (Scopus)

• Approximability of the subset sum reconfiguration problem

  Ito, T. & Demaine, E. D., 2014 10月, In: Journal of Combinatorial Optimization. 28, 3, p. 639-654 16 p.

  研究成果: Article › 査読

  • Knapsack 100%
  • Conflict Graph 66%
  • Optimization 33%
  • Polynomial Time 33%
  • Reconfiguration 33%
  15 被引用数 (Scopus)

• Base-object location problems for base-monotone regions

  Chun, J., Horiyama, T., Ito, T., Kaothanthong, N., Ono, H., Otachi, Y., Tokuyama, T., Uehara, R. & Uno, T., 2014, In: Theoretical Computer Science. 555, C, p. 71-84 14 p.

  研究成果: Article › 査読

  • Polynomial Time 100%
  • Approximation Algorithms 100%
  • Shortest Path 100%
  • Image Segmentation 100%
  • Complexity Result 100%

• Complexity of finding maximum regular induced subgraphs with prescribed degree

  Asahiro, Y., Eto, H., Ito, T. & Miyano, E., 2014, In: Theoretical Computer Science. 550, C, p. 21-35 15 p.

  研究成果: Article › 査読

  • Graph 100%
  • Approximates 33%
  • Constant 33%
  • Polynomial Time 16%
  • Running Time 16%
  6 被引用数 (Scopus)

• Generalized rainbow connectivity of graphs

  Uchizawa, K., Aoki, T., Ito, T. & Zhou, X., 2014, In: Theoretical Computer Science. 555, C, p. 35-42 8 p.

  研究成果: Article › 査読

  • Edge 100%
  • Graph 83%
  • Computational 16%
  • Polynomial Time 16%
  • Nonnegative Integer 16%

• On the minimum caterpillar problem in digraphs

  Okada, T., Suzuki, A., Ito, T. & Zhou, X., 2014, In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences. E96-A, 3, p. 848-857 10 p.

  研究成果: Article › 査読

  • Leaf 100%
  • Linear Time 50%
  • Directed Path 50%
  • Algorithm 50%
  • Number 50%

• Reconfiguration of list L(2, 1)-labelings in a graph

  Ito, T., Kawamura, K., Ono, H. & Zhou, X., 2014, In: Theoretical Computer Science. 544, C, p. 84-97 14 p.

  研究成果: Article › 査読

  • Graph 100%
  • Vertex 100%
  • Trees 50%
  • Linear Time 25%
  • Sufficient Condition 25%
  15 被引用数 (Scopus)

• The list coloring reconfiguration problem for bounded pathwidth graphs

  Hatanaka, T., Ito, T. & Zhou, X., 2014, In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8881, p. 314-328 15 p.

  研究成果: Article › 査読

  • Coloring 100%
  • Planar Graph 50%
  • Polynomial Time Algorithm 25%
  • Reconfiguration Problem 25%
  • Subclasses 25%
  2 被引用数 (Scopus)

• The minimum vulnerability problem on graphs

  Aoki, Y., Halldórsson, B. V., Halldórsson, M. M., Ito, T., Konrad, C. & Zhou, X., 2014 1月 1, In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8881, p. 299-313 15 p.

  研究成果: Article › 査読

  • Edge 100%
  • Graph 75%
  • Directed Graphs 50%
  • Vulnerabilities 50%
  • Nonnegative Integer 25%
  2 被引用数 (Scopus)

• The minimum vulnerability problem on graphs

  Aoki, Y., Halld´Orsson, B. V., Halld´Orsson, MU. M., Ito, T., Konrad, C. & Zhou, X., 2014, In: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 8881, p. 131-299 169 p.

  研究成果: Article › 査読

  • Graph 100%
  • Edge 66%
  • Path Problem 33%
  • Algorithm 33%
  • Number 33%
  1 被引用数 (Scopus)
• 2013

  On the rainbow connectivity of graphs: Complexity and FPT algorithms

  Uchizawa, K., Aoki, T., Ito, T., Suzuki, A. & Zhou, X., 2013 10月, In: Algorithmica. 67, 2, p. 161-179 19 p.

  研究成果: Article › 査読

  • Graph 100%
  • Edge 83%
  • Coloring 66%
  • Algorithm 50%
  • Vertex 50%
  28 被引用数 (Scopus)

• Route-enabling graph orientation problems

  Ito, T., Miyamoto, Y., Ono, H., Tamaki, H. & Uehara, R., 2013 2月, In: Algorithmica. 65, 2, p. 317-338 22 p.

  研究成果: Article › 査読

  • Edge 100%
  • Polynomial Time 75%
  • Planar Graph 50%
  • Graph 50%
  • Minimizes 50%
• 2012

  An improved sufficient condition for reconfiguration of list edge-colorings in a tree

  Ito, T., Kawamura, K. & Zhou, X., 2012 3月, In: IEICE Transactions on Information and Systems. E95-D, 3, p. 737-745 9 p.

  研究成果: Article › 査読

  • Edge 100%
  • Sufficient Condition 83%
  • Coloring 66%
  • Trees 50%
  • Reconfiguration 33%
  13 被引用数 (Scopus)

• Minimum cost partitions of trees with supply and demand

  Ito, T., Hara, T., Zhou, X. & Nishizeki, T., 2012 11月, In: Algorithmica. 64, 3, p. 400-415 16 p.

  研究成果: Article › 査読

  • Vertex 100%
  • Edge 71%
  • Direction 42%
  • Positive Integer 28%
  • Trees 28%
  8 被引用数 (Scopus)

• Partitioning aweighted tree into subtrees with weights in a given range

  Ito, T., Nishizeki, T., Schröder, M., Uno, T. & Zhou, X., 2012 4月 1, In: Algorithmica. 62, 3-4, p. 823-841 19 p.

  研究成果: Article › 査読

  • Partition 100%
  • Trees 22%
  • Weights 22%
  • Graph 22%
  • Number 22%
  9 被引用数 (Scopus)

• Reconfiguration of list edge-colorings in a graph

  Ito, T., Kamiski, M. & Demaine, E. D., 2012 10月, In: Discrete Applied Mathematics. 160, 15, p. 2199-2207 9 p.

  研究成果: Article › 査読

  • Edge 100%
  • Coloring 66%
  • Sufficient Condition 33%
  • Trees 22%
  • Graph 22%
  52 被引用数 (Scopus)
• 2011

  Minimum cost edge-colorings of trees can be reduced to matchings

  Ito, T., Sakamoto, N., Zhou, X. & Nishizeki, T., 2011 2月, In: IEICE Transactions on Information and Systems. E94-D, 2, p. 190-195 6 p.

  研究成果: Article › 査読

  • Edge 100%
  • Coloring 70%
  • Trees 20%
  • Polynomial Time 10%
  • Integer 10%

• On disconnected cuts and separators

  Ito, T., Kamiski, M., Paulusma, D. & Thilikos, D. M., 2011 8月 6, In: Discrete Applied Mathematics. 159, 13, p. 1345-1351 7 p.

  研究成果: Article › 査読

  • Graph 100%
  • Induced Subgraph 66%
  • Complete 66%
  • Testing 66%
  • Show 66%
  9 被引用数 (Scopus)

• On the complexity of reconfiguration problems

  Ito, T., Demaine, E. D., Harvey, N. J. A., Papadimitriou, C. H., Sideri, M., Uehara, R. & Uno, Y., 2011, In: Theoretical Computer Science. 412, 12-14, p. 1054-1065 12 p.

  研究成果: Article › 査読

  • Reconfiguration Problem 100%
  • Polynomial Time 33%
  • Reconfiguration 33%
  • Feasible Solution 33%
  • Complete Problem 33%
  189 被引用数 (Scopus)

• Parameterizing cut sets in a graph by the number of their components

  Ito, T., Kamiński, M., Paulusma, D. & Thilikos, D. M., 2011 10月 21, In: Theoretical Computer Science. 412, 45, p. 6340-6350 11 p.

  研究成果: Article › 査読

  • Graph 100%
  • Complete 50%
  • Algorithm 33%
  • Classes 33%
  • Subgraphs 33%
  9 被引用数 (Scopus)