TOHOKU UNIVERSITY Researchers

Details of the Researcher

Home

日本語 English

Takehiro Ito

Section

Graduate School of Information Sciences

Job title

Professor

Degree

Ph.D. in Information Science (Tohoku University)

researchmap

https://researchmap.jp/takehiroito

J-GLOBAL ID

200901086150191670

e-Rad No.

40431548

Research History 9

2020/05 - Present

Graduate School of Information Sciences, Tohoku University　Professor
2020/04 - 2024/03

Tohoku University
2012/01 - 2020/04

Graduate School of Information Sciences, Tohoku University　Associate Professor
2007/04 - 2011/12

Graduate School of Information Sciences, Tohoku University　Assistant Professor
2008/10 - 2009/03

Université Libre de Bruxelles　Visiting Researcher
2008/03 - 2008/06

McGill University　Visiting Researcher
2006/04 - 2007/03

Graduate School of Information Sciences, Tohoku University　Research Associate
2003/04 - 2006/03

Japan Society for the Promotion of Science　Research Fellow (DC1)
2005/06 - 2005/10

Massachusetts Institute of Technology　Visiting Student

Show all Show first 5

Education 3

Tohoku University　Graduate School of Information Sciences　Department of System Information Sciences

2003/04 - 2006/03
Tohoku University　Graduate School of Information Sciences　Department of System Information Sciences

2001/10 - 2003/03
Tohoku University　Faculty of Engineering　Information Engineering

1998/04 - 2001/09

Committee Memberships 9

Asian Association for Algorithms and Computation　Board Member

2025/05 - Present
LA Symposium　Chair of FY2025

2025/04 - Present
European Association for Theoretical Computer Science, Japan Chapter　Vice Chair

2019/02 - Present
National Institute of Science and Technology Policy (NISTEP), Center for S&T Foresight and Indicators　Specialized Investigator

2016/04 - Present
情報処理学会アルゴリズム研究運営委員会　運営委員

2018/04 - 2022/04
European Association for Theoretical Computer Science, Japan Chapter　Secretary

2014/01 - 2019/01
電子情報通信学会コンピュテーション研究専門委員会　専門委員

2012/06 - 2018/05
文部科学省科学技術・学術政策研究所科学技術動向研究センター　専門調査員

2014/04 - 2016/03
電子情報通信学会コンピュテーション研究専門委員会　幹事

2010/05 - 2012/05

Show all ︎Show first 5

Professional Memberships 2

The Institute of Electronics, Information and Communication Engineers
Information Processing Society of Japan

Research Interests 2

combinatorial reconfiguration
graph algorithm

Research Areas 1

Informatics / Information theory /

Awards 16

FIT2020 Funai Best Paper Award

2021/08　The Funai Foundation for Information Technology
山下記念研究賞

2020/03　情報処理学会
Incentive Award

2018/11　M.Ishida Foundation
Funai Information Technology Award

2018/04　The Funai Foundation for Information Technology
The Young Scientists' Prize of the Commendation for Science and Technology

2018/04　The Minister of Education, Culture, Sports, Science and Technology
RIEC Award for Tohoku University Researcher

2013/11/21　電気通信工学振興会
Funai Information Technology Incentive Award

2009/04/18　船井情報科学振興財団
Best Paper Award of ISAAC 2008

2008/12/16　The 19th International Symposium on Algorithms and Computation
McGill-Japan Visiting Scholar Awards 2008

2007/11　McGill University
Noguchi Incentive Award

2007/05/09　情報処理学会東北支部
Best PhD

2006/03　東北大学大学院情報科学研究科
Best PhD

2006/03　東北大学
Aoba Foundation for the Promotion of Engineering, Incentive Award

2005/12/14　青葉工学振興会
Young C&C Author's Prize

2004/01/28　C&C振興財団
TELECOM System Technology Award for Student

2003/03　電気通信普及財団
LA Best Presentation Award

2002/02　LAシンポジウム

Show all ︎Show 5

Papers 152

Independent set reconfiguration under bounded-hop token jumping Invited Peer-reviewed

Hiroki Hatano, Naoki Kitamura, Taisuke Izumi, Takehiro Ito, Toshimitsu Masuzawa

Theoretical Computer Science　1062　115651　2026/02/02

DOI： 10.1016/j.tcs.2025.115651 　
Reconfiguration of time-respecting arborescences Peer-reviewed

Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira Suzuki

Algorithmica　88　(1)　15　2026/02

DOI： 10.1007/s00453-025-01365-1 　
Minimum sum coloring with bundles in trees and bipartite graphs Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Proceedings of the 36th International Symposium on Algorithms and Computation (ISAAC 2025)　359　40:1-40:14　2025/11/27

DOI： 10.4230/LIPIcs.ISAAC.2025.40 　
Multi-objective combinatorial reconfiguration considering cost and length by answer set programming: Algorithms, encodings, and empirical analysis International-coauthorship Peer-reviewed

Kazuki Takada, Mutsunori Banbara, Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Torsten Schaub, Ryuhei Uehara

Proceedings of the 28th European Conference on Artificial Intelligence (ECAI 2025)　413　1575-1582　2025/10/21
Publisher: IOS Press
DOI： 10.3233/faia250982 　

ISSN： 0922-6389

eISSN： 1879-8314

More details Close

We introduce the Multi-Objective Combinatorial Reconfiguration Optimization Problem (MO-CROP), and propose an Answer Set Programming (ASP) based approach for its solution. MO-CROP involves finding the Pareto-optimal sequences (or Pareto front) of adjacent feasible solutions between two given feasible solutions of a combinatorial problem, considering both cost and length. Our algorithm is compactly implemented through multi-shot ASP solving, and its implementing solver optirecon provides an effective tool for solving MO-CROP. As a concrete example of MO-CROP, we present an ASP encoding for solving the multi-objective independent set reconfiguration optimization problem. Experimental results on the benchmark set from the recent CoRe Challenge demonstrate our approach’s ability to capture diverse optimal sequences that reveal trade-offs between cost and length, a capability often lacking in traditional combinatorial reconfiguration methods.
Minimum sum coloring with bundles in trees and bipartite graphs

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

CoRR　abs/2509.15080　2025/09/18

DOI： 10.48550/arXiv.2509.15080 　
Algorithmic theory of qubit routing in the linear nearest neighbor architectures Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

ACM Transactions on Quantum Computing　6　(3)　19　2025/05/30
Publisher: Association for Computing Machinery (ACM)
DOI： 10.1145/3722119 　

ISSN： 2643-6809

eISSN： 2643-6817
Reconfiguration of colorings in triangulations of the sphere Peer-reviewed

Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

Journal of Computational Geometry　16　(1)　253-294　2025/04/10

DOI： 10.20382/jocg.v16i1a8 　
Reforming an envy-free matching Peer-reviewed

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

Algorithmica　87　(4)　594-620　2025/04

DOI： 10.1007/s00453-025-01294-z 　
Rerouting planar curves and disjoint paths Peer-reviewed

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

ACM Transactions on Algorithms　21　(2)　20　2025/03/13
Publisher: Association for Computing Machinery (ACM)
DOI： 10.1145/3715694 　

ISSN： 1549-6325

eISSN： 1549-6333
Independent set reconfiguration under bounded-hop token jumping Peer-reviewed

Hiroki Hatano, Naoki Kitamura, Taisuke Izumi, Takehiro Ito, Toshimitsu Masuzawa

Proceedings of the 19th International Conference and Workshops on Algorithms and Computation (WALCOM 2025)　15411　215-228　2025/02

DOI： 10.1007/978-981-96-2845-2_14 　
Multifaceted evaluation of distribution network configurations to minimize remaining power outage Peer-reviewed

Shuhei Sugimura, Akihisa Kaneko, Yasuhiro Hayashi, Teppei Nozaki, Akira Suzuki, Takehiro Ito, Takayuki Tanabe

IEEJ Transactions on Power and Energy　144　(12)　640-649　2024/12/01
Publisher: Institute of Electrical Engineers of Japan (IEE Japan)
DOI： 10.1541/ieejpes.144.640 　

ISSN： 0385-4213

eISSN： 1348-8147
Algorithmic meta-theorems for combinatorial reconfiguration revisited Peer-reviewed

Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi

Algorithmica　86　(11)　3395-3424　2024/11

DOI： 10.1007/s00453-024-01261-0 　
Reconfiguration of vertex-disjoint shortest paths on graphs Peer-reviewed

Rin Saito, Hiroshi Eto, Takehiro Ito, Ryuhei Uehara

Journal of Graph Algorithms and Applications　28　(3)　87-101　2024/09

DOI： 10.7155/jgaa.v28i3.2973 　
Independent set reconfiguration under bounded-hop token

Hiroki Hatano, Naoki Kitamura, Taisuke Izumi, Takehiro Ito, Toshimitsu Masuzawa

CoRR　abs/2407.11768　2024/07

DOI： 10.48550/arXiv.2407.11768 　
Scalable hard instances for independent set reconfiguration Peer-reviewed

Takehide Soh, Takumu Watanabe, Jun Kawahara, Akira Suzuki, Takehiro Ito

Proceedings of the 22nd International Symposium on Experimental Algorithms (SEA 2024)　301　26:1-26:15　2024/07
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
DOI： 10.4230/LIPIcs.SEA.2024.26 　
CoRe challenge 2022/2023: Empirical evaluations for independent set reconfiguration problems (Extended abstract) Peer-reviewed

Takehide Soh, Tomoya Tanjo, Yoshio Okamoto, Takehiro Ito

Proceedings of the 17th International Symposium on Combinatorial Search (SoCS 2024)　17　285-286　2024/06
Publisher: AAAI Press
DOI： 10.1609/socs.v17i1.31583 　
Solving reconfiguration problems of first-order expressible properties of graph vertices with Boolean satisfiability Peer-reviewed

Takahisa Toda, Takehiro Ito, Jun Kawahara, Takehide Soh, Akira Suzuki, Junichi Teruyama

Proceedings of the 35th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2023)　294-302　2023/12
Publisher: IEEE
DOI： 10.1109/ICTAI59109.2023.00050 　
On reachable assignments under dichotomous preferences Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

Theoretical Computer Science　979　114196　2023/11

DOI： 10.1016/j.tcs.2023.114196 　
Sorting balls and water: Equivalence and computational complexity Peer-reviewed

Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka

Theoretical Computer Science　978　114158　2023/11

DOI： 10.1016/j.tcs.2023.114158 　
Happy set problem on subclasses of co-comparability graphs Peer-reviewed

Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura

Algorithmica　85　(11)　3327-3347　2023/11

DOI： 10.1007/s00453-022-01081-0 　
Reconfiguration of spanning trees with degree constraints or diameter constraints Peer-reviewed

Nicolas Bousque, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, Kunihiro Wasa

Algorithmica　85　(9)　2779-2816　2023/09

DOI： 10.1007/s00453-023-01117-z 　
Algorithmic theory of qubit routing Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023)　14079　533-546　2023/07

DOI： 10.1007/978-3-031-38906-1_35 　
Reconfiguration of time-respecting arborescences Peer-reviewed

Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira Suzuki

Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023)　14079　521-532　2023/07

DOI： 10.1007/978-3-031-38906-1_34 　
Hardness of finding combinatorial shortest paths on graph associahedra Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto

Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023)　261　82:1-82:17　2023/07

DOI： 10.4230/LIPIcs.ICALP.2023.82 　
Rerouting planar curves and disjoint paths Peer-reviewed

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP 2023)　81:1-81:19　2023/07

DOI： 10.4230/LIPIcs.ICALP.2023.81 　
Reconfiguration of cliques in a graph Peer-reviewed

Takehiro Ito, Hirotaka Ono, Yota Otachi

Discrete Applied Mathematics　333　43-58　2023/07

DOI： 10.1016/j.dam.2023.01.026 　
Reconfiguration of colorings in triangulations of the sphere Peer-reviewed

Takehiro Ito, Yuni Iwamasa, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

Proceedings of the 39th International Symposium on Computational Geometry (SoCG 2023)　258　43:1-43:16　2023/06

DOI： 10.4230/LIPIcs.SoCG.2023.43 　
ZDD-based algorithmic framework for solving shortest reconfiguration problems Peer-reviewed

Takehiro Ito, Jun Kawahara, Yu Nakahata, Takehide Soh, Akira Suzuki, Junichi Teruyama, Takahisa Toda

Proceedings of the 20th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR 2023)　13884　167-183　2023/05

DOI： 10.1007/978-3-031-33271-5_12 　
Fixed-parameter algorithms for graph constraint logic Peer-reviewed

Tatsuhiko Hatanaka, Felix Hommelsheim, Takehiro Ito, Yusuke Kobayashi, Moritz Mühlenthaler, Akira Suzuki

Theoretical Computer Science　959　113863　2023/05

DOI： 10.1016/j.tcs.2023.113863 　
Reconfiguration of vertex-disjoint shortest paths on graphs Peer-reviewed

Rin Saito, Hiroshi Eto, Takehiro Ito, Ryuhei Uehara

Proceedings of the 17th International Conference and Workshops on Algorithms and Computation (WALCOM 2023)　13973　191-201　2023/03

DOI： 10.1007/978-3-031-27051-2_17 　
Reconfiguring (non-spanning) arborescences Peer-reviewed

Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa

Theoretical Computer Science　943　131-141　2023/01

DOI： 10.1016/j.tcs.2022.12.007 　
Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams Peer-reviewed

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

ACM Transactions on Algorithms　19　(1)　6　2023/01

DOI： 10.1145/3561302 　
Approximability of the distance independent set problem on regular graphs and planar graphs Peer-reviewed

Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences　105-A　(9)　1211-1222　2022/09

DOI： 10.1587/transfun.2021dmp0017 　
Happy set problem on subclasses of co-comparability graphs Peer-reviewed

Hiroshi Eto, Takehiro Ito, Eiji Miyano, Akira Suzuki, Yuma Tamura

WALCOM: Algorithms and Computation - 16th International Conference and Workshops (WALCOM)　149-160　2022
Publisher: Springer
DOI： 10.1007/978-3-030-96731-4_13 　
Reconfiguration of regular induced subgraphs Peer-reviewed

Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, Kunihiro Wasa

WALCOM: Algorithms and Computation - 16th International Conference and Workshops (WALCOM)　35-46　2022
Publisher: Springer
DOI： 10.1007/978-3-030-96731-4_4 　
Invitation to combinatorial reconfiguration Invited

Takehiro Ito

WALCOM: Algorithms and Computation - 16th International Conference and Workshops (WALCOM)　26-31　2022
Publisher: Springer
DOI： 10.1007/978-3-030-96731-4_3 　
Reconfiguration of spanning trees with degree constraint or diameter constraint Peer-reviewed

Nicolas Bousquet, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Paul Ouvrard, Akira Suzuki, Kunihiro Wasa

39th International Symposium on Theoretical Aspects of Computer Science (STACS)　15:1-15:21　2022
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
DOI： 10.4230/LIPIcs.STACS.2022.15 　
Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams Peer-reviewed

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Shun-ichi Maezawa, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms (SODA)　1342-1355　2022
Publisher: SIAM
DOI： 10.1137/1.9781611977073.56 　
Sorting balls and water: Equivalence and computational complexity Peer-reviewed

Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka

11th International Conference on Fun with Algorithms (FUN)　16:1-16:17　2022
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
DOI： 10.4230/LIPIcs.FUN.2022.16 　
Invitation to combinatorial reconfiguration (Invited Talk) Invited

Takehiro Ito

CPM　1-1　2022

DOI： 10.4230/LIPIcs.CPM.2022.1 　
Reforming an envy-free matching Peer-reviewed

Takehiro Ito, Yuni Iwamasa, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yuta Nozaki, Yoshio Okamoto, Kenta Ozeki

AAAI　5084-5091　2022

DOI： 10.1609/aaai.v36i5.20441 　
Shortest reconfiguration of perfect matchings via alternating cycles Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

SIAM Journal on Discrete Mathematics　36　(2)　1102-1123　2022

DOI： 10.1137/20m1364370 　
A parameterized view to the robust recoverable base problem of matroids under structural uncertainty Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Operations Research Letters　50　(3)　370-375　2022

DOI： 10.1016/j.orl.2022.05.001 　
Incremental optimization of independent sets under the reconfiguration framework Peer-reviewed

Takehiro Ito, Haruka Mizuta, Naomi Nishimura, Akira Suzuki

Journal of Combinatorial Optimization　43　(5)　1264-1279　2022

DOI： 10.1007/s10878-020-00630-z 　
Reconfiguring directed trees in a digraph Peer-reviewed

Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa

Computing and Combinatorics - 27th International Conference (COCOON)　343-354　2021
Publisher: Springer
DOI： 10.1007/978-3-030-89543-3_29 　
Algorithms for gerrymandering over graphs Peer-reviewed

Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Theoretical Computer Science　868　30-45　2021

DOI： 10.1016/j.tcs.2021.03.037 　
Approximability of the independent feedback vertex set problem for bipartite graphs Peer-reviewed

Yuma Tamura, Takehiro Ito, Xiao Zhou

Theoretical Computer Science　849　227-236　2021

DOI： 10.1016/j.tcs.2020.10.026 　
Parameterized complexity of independent set reconfiguration problems Peer-reviewed

Takehiro Ito, Marcin Kamiński, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, Katsuhisa Yamanaka

Discrete Applied Mathematics　283　336-345　2020/09
Publisher: Elsevier BV
DOI： 10.1016/j.dam.2020.01.022 　

ISSN： 0166-218X
Reconfiguring spanning and induced subgraphs Peer-reviewed

Tesshu Hanaka, Takehiro Ito, Haruka Mizuta, Benjamin Moore, Naomi Nishimura, Vijay Subramanya, Akira Suzuki, Krishna Vaidyanathan

Theoretical Computer Science　806　553-566　2020/02

DOI： 10.1016/j.tcs.2019.09.018 　
Approximability of the independent feedback vertex set problem for bipartite graphs Peer-reviewed

Yuma Tamura, Takehiro Ito, Xiao Zhou

Proceedings of the 14th International Conference and Workshop on Algorithms and Computation (WALCOM 2020), Lecture Notes in Computer Science　12049　286-295　2020

DOI： 10.1007/978-3-030-39881-1_24 　
Shortest reconfiguration of colorings under Kempe changes Peer-reviewed

Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, Kunihiro Wasa

Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020), Leibniz International Proceedings in Informatics　154　35:1-35:14　2020

DOI： 10.4230/LIPIcs.STACS.2020.35 　
Reconfiguration of colorable sets in classes of perfect graphs Peer-reviewed

Takehiro Ito, Yota Otachi

Theoretical Computer Science　772　111-122　2019/06

DOI： 10.1016/j.tcs.2018.11.024 　
The coloring reconfiguration problem on specific graph classes Peer-reviewed

Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

IEICE Trans. on Information and Systems　102-D　(3)　423-429　2019/03

DOI： 10.1587/transinf.2018FCP0005 　
Reconfiguration of maximum-weight b-matchings in a graph Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Journal of Combinatorial Optimization　37　(2)　454-464　2019/02

DOI： 10.1007/s10878-018-0289-3 　
Shortest reconfiguration of matchings Peer-reviewed

Nicolas Bousquet, Tatsuhiko Hatanaka, Takehiro Ito, Moritz Mühlenthaler

Proceedings of the 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2019)　11789　162-174　2019

DOI： 10.1007/978-3-030-30786-8_13 　
The perfect matching reconfiguration problem Peer-reviewed

Marthe Bonamy, Nicolas Bousquet, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Arnaud Mary, Moritz Mühlenthaler, Kunihiro Wasa

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)　138　80:1-80:14　2019

DOI： 10.4230/LIPIcs.MFCS.2019.80 　
Reconfiguration of minimum Steiner trees via vertex exchanges Peer-reviewed

Haruka Mizuta, Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

Proceedings of the 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)　138　79:1-79:11　2019

DOI： 10.4230/LIPIcs.MFCS.2019.79 　
Shortest reconfiguration of perfect matchings via alternating cycles Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Proceedings of the 27th Annual European Symposium on Algorithms (ESA 2019), Leibniz International Proceedings in Informatics　144　61:1-61:15　2019

DOI： 10.4230/LIPIcs.ESA.2019.61 　
Incremental optimization of independent sets under the reconfiguration framework Peer-reviewed

Takehiro Ito, Haruka Mizuta, Naomi Nishimura, Akira Suzuki

Proceedings of the 25th International Computing and Combinatorics Conference (COCOON 2019)　11653　313-324　2019

DOI： 10.1007/978-3-030-26176-4_26 　
Diameter of colorings under Kempe changes Peer-reviewed

Marthe Bonamy, Marc Heinrich, Takehiro Ito, Yusuke Kobayashi, Haruka Mizuta, Moritz Mühlenthaler, Akira Suzuki, Kunihiro Wasa

Proceedings of the 25th International Computing and Combinatorics Conference (COCOON 2019)　11653　52-64　2019

DOI： 10.1007/978-3-030-26176-4_5 　
Algorithms for gerrymandering over graphs Peer-reviewed

Takehiro Ito, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS 2019)　1413-1421　2019
Minimum-cost b-edge dominating sets on trees Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Algorithmica　81　(1)　343-366　2019/01

DOI： 10.1007/s00453-018-0448-z 　
Reconfiguration of colorable sets in classes of perfect graphs Peer-reviewed

Takehiro Ito, Yota Otachi

Proceedings of the 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)　101　27:1-27:13　2018
Algorithms for coloring reconfiguration under recolorability constraints. Peer-reviewed

Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC 2018)　123　37:1-37:13　2018

DOI： 10.4230/LIPIcs.ISAAC.2018.37 　
The complexity of (list) edge-coloring reconfiguration problem Peer-reviewed

Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

IEICE Transactions　101-A　(1)　232-238　2018

DOI： 10.1587/transfun.E101.A.232 　
Parameterized complexity of the list coloring reconfiguration problem with graph parameters Peer-reviewed

Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

Theoretical Computer Science　739　65-79　2018

DOI： 10.1016/j.tcs.2018.05.005 　
Reconfiguring spanning and induced subgraphs Peer-reviewed

Tesshu Hanaka, Takehiro Ito, Haruka Mizuta, Benjamin Moore, Naomi Nishimura, Vijay Subramanya, Akira Suzuki, Krishna Vaidyanathan

Computing and Combinatorics - 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018, Proceedings　428-440　2018

DOI： 10.1007/978-3-319-94776-1_36 　
Complexity of tiling a polygon with trominoes or bars Peer-reviewed

Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, Ryuhei Uehara

Discrete & Computational Geometry　58　(3)　686-704　2017

DOI： 10.1007/s00454-017-9884-9 　
Reconfiguration of Steiner trees in an unweighted graph Peer-reviewed

Haruka Mizuta, Takehiro Ito, Xiao Zhou

IEICE Transactions　100-A　(7)　1532-1540　2017

DOI： 10.1587/transfun.E100.A.1532 　
Efficient stabilization of cooperative matching games Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Theoretical Computer Science　677　69-82　2017

DOI： 10.1016/j.tcs.2017.03.020 　
Tight approximability of the server allocation problem for real-time applications Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto, Taichi Shiitada

Algorithmic Aspects of Cloud Computing - Third International Workshop, ALGOCLOUD 2017, Vienna, Austria, September 5, 2017, Revised Selected Papers　41-55　2017

DOI： 10.1007/978-3-319-74875-7_4 　
The coloring reconfiguration problem on specific graph classes Peer-reviewed

Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

Combinatorial Optimization and Applications - 11th International Conference, COCOA 2017, Shanghai, China, December 16-18, 2017, Proceedings, Part I　152-162　2017

DOI： 10.1007/978-3-319-71150-8_15 　
Reconfiguration of maximum-weight b-matchings in a graph Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Computing and Combinatorics - 23rd International Conference, COCOON 2017, Hong Kong, China, August 3-5, 2017, Proceedings　287-296　2017

DOI： 10.1007/978-3-319-62389-4_24 　
Complexity of the multi-service center problem Peer-reviewed

Takehiro Ito, Naonori Kakimura, Yusuke Kobayashi

28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand　48:1-48:12　2017

DOI： 10.4230/LIPIcs.ISAAC.2017.48 　
Complexity of coloring reconfiguration under recolorability constraints Peer-reviewed

Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

28th International Symposium on Algorithms and Computation, ISAAC 2017, December 9-12, 2017, Phuket, Thailand　62:1-62:12　2017

DOI： 10.4230/LIPIcs.ISAAC.2017.62 　
Parameterized complexity of the list coloring reconfiguration problem with graph parameters Peer-reviewed

Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark　51:1-51:13　2017

DOI： 10.4230/LIPIcs.MFCS.2017.51 　
Approximation algorithm for the distance-3 independent set problem on cubic graphs Peer-reviewed

Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano

WALCOM: Algorithms and Computation, 11th International Conference and Workshops, WALCOM 2017, Hsinchu, Taiwan, March 29-31, 2017, Proceedings.　228-240　2017

DOI： 10.1007/978-3-319-53925-6_18 　
The complexity of (list) edge-coloring reconfiguration problem Peer-reviewed

Hiroki Osawa, Akira Suzuki, Takehiro Ito, Xiao Zhou

WALCOM: Algorithms and Computation, 11th International Conference and Workshops, WALCOM 2017, Hsinchu, Taiwan, March 29-31, 2017, Proceedings.　347-358　2017

DOI： 10.1007/978-3-319-53925-6_27 　
A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares Peer-reviewed

Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

Computational Geometry: Theory and Applications　51　25-39　2016

DOI： 10.1016/j.comgeo.2015.10.004 　
Reconfiguration of vertex covers in a graph Peer-reviewed

Takehiro Ito, Hiroyuki Nooka, Xiao Zhou

IEICE Transactions　99-D　(3)　598-606　2016

DOI： 10.1587/transinf.2015FCP0010 　
The minimum vulnerability problem on specific graph classes Peer-reviewed

Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou

Journal of Combinatorial Optimization　32　(4)　1288-1304　2016

DOI： 10.1007/s10878-015-9950-2 　
The complexity of dominating set reconfiguration Peer-reviewed

Arash Haddadan, Takehiro Ito, Amer E. Mouawad, Naomi Nishimura, Hirotaka Ono, Akira Suzuki, Youcef Tebbal

Theoretical Computer Science　651　37-49　2016

DOI： 10.1016/j.tcs.2016.08.016 　
Efficient stabilization of cooperative matching games Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, Singapore, May 9-13, 2016　41-49　2016
Approximability of the distance independent set problem on regular graphs and planar graphs Peer-reviewed

Hiroshi Eto, Takehiro Ito, Zhilong Liu, Eiji Miyano

Combinatorial Optimization and Applications - 10th International Conference, COCOA 2016, Hong Kong, China, December 16-18, 2016, Proceedings　270-284　2016

DOI： 10.1007/978-3-319-48749-6_20 　
Reconfiguration of Steiner trees in an unweighted graph Peer-reviewed

Haruka Mizuta, Takehiro Ito, Xiao Zhou

Combinatorial Algorithms - 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings　163-175　2016

DOI： 10.1007/978-3-319-44543-4_13 　
Experimental evaluations of dynamic algorithm for maintaining shortest-paths trees on real-world networks Peer-reviewed

Takashi Hasegawa, Takehiro Ito, Akira Suzuki, Xiao Zhou

Interdisciplinary Information Sciences　21　(1)　25-35　2015

DOI： 10.4036/iis.2015.25 　
The list coloring reconfiguration problem for bounded pathwidth graphs Peer-reviewed

Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

IEICE Transactions　98-A　(6)　1168-1178　2015

DOI： 10.1587/transfun.E98.A.1168 　
Algorithms for the independent feedback vertex set problem Peer-reviewed

Yuma Tamura, Takehiro Ito, Xiao Zhou

IEICE Transactions　98-A　(6)　1179-1188　2015

DOI： 10.1587/transfun.E98.A.1179 　
Swapping labeled tokens on graphs Peer-reviewed

Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, Takeaki Uno

Theoretical Computer Science　586　81-94　2015

DOI： 10.1016/j.tcs.2015.01.052 　
Linear-time algorithm for sliding tokens on trees Peer-reviewed

Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada

Theoretical Computer Science　600　132-142　2015

DOI： 10.1016/j.tcs.2015.07.037 　
Reconfiguration of cliques in a graph Peer-reviewed

Takehiro Ito, Hirotaka Ono, Yota Otachi

Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, Proceedings　212-223　2015

DOI： 10.1007/978-3-319-17142-5_19 　
The complexity of dominating set reconfiguration Peer-reviewed

Arash Haddadan, Takehiro Ito, Amer E. Mouawad, Naomi Nishimura, Hirotaka Ono, Akira Suzuki, Youcef Tebbal

Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings　398-409　2015

DOI： 10.1007/978-3-319-21840-3_33 　
Competitive diffusion on weighted graphs Peer-reviewed

Takehiro Ito, Yota Otachi, Toshiki Saitoh, Hisayuki Satoh, Akira Suzuki, Kei Uchizawa, Ryuhei Uehara, Katsuhisa Yamanaka, Xiao Zhou

Algorithms and Data Structures - 14th International Symposium, WADS 2015, Victoria, BC, Canada, August 5-7, 2015. Proceedings　422-433　2015

DOI： 10.1007/978-3-319-21840-3_35 　
On the minimum caterpillar problem in digraphs Peer-reviewed

Taku Okada, Akira Suzuki, Takehiro Ito, Xiao Zhou

IEICE Transactions　97-A　(3)　848-857　2014

DOI： 10.1587/transfun.E97.A.848 　
Approximability of the subset sum reconfiguration problem Peer-reviewed

Takehiro Ito, Erik D. Demaine

Journal of Combinatorial Optimization　28　(3)　639-654　2014

DOI： 10.1007/s10878-012-9562-z 　
A 4.31-approximation for the geometric unique coverage problem on unit disks Peer-reviewed

Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

Theoretical Computer Science　544　14-31　2014

DOI： 10.1016/j.tcs.2014.04.014 　
Reconfiguration of list L(2,1)-labelings in a graph Peer-reviewed

Takehiro Ito, Kazuto Kawamura, Hirotaka Ono, Xiao Zhou

Theoretical Computer Science　544　84-97　2014

DOI： 10.1016/j.tcs.2014.04.011 　
Complexity of finding maximum regular induced subgraphs with prescribed degree Peer-reviewed

Yuichi Asahiro, Hiroshi Eto, Takehiro Ito, Eiji Miyano

Theoretical Computer Science　550　21-35　2014

DOI： 10.1016/j.tcs.2014.07.008 　
Generalized rainbow connectivity of graphs Peer-reviewed

Kei Uchizawa, Takanori Aoki, Takehiro Ito, Xiao Zhou

Theoretical Computer Science　555　35-42　2014

DOI： 10.1016/j.tcs.2014.01.007 　
Base-object location problems for base-monotone regions Peer-reviewed

Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno

Theoretical Computer Science　555　71-84　2014

DOI： 10.1016/j.tcs.2013.11.030 　
The minimum vulnerability problem on graphs Peer-reviewed

Yusuke Aoki, Bjarni V. Halldórsson, Magnús M. Halldórsson, Takehiro Ito, Christian Konrad, Xiao Zhou

Combinatorial Optimization and Applications - 8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014, Proceedings　299-313　2014

DOI： 10.1007/978-3-319-12691-3_23 　
The list coloring reconfiguration problem for bounded pathwidth graphs Peer-reviewed

Tatsuhiko Hatanaka, Takehiro Ito, Xiao Zhou

Combinatorial Optimization and Applications - 8th International Conference, COCOA 2014, Wailea, Maui, HI, USA, December 19-21, 2014, Proceedings　314-328　2014

DOI： 10.1007/978-3-319-12691-3_24 　
Swapping labeled tokens on graphs Peer-reviewed

Katsuhisa Yamanaka, Erik D. Demaine, Takehiro Ito, Jun Kawahara, Masashi Kiyomi, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Kei Uchizawa, Takeaki Uno

Fun with Algorithms - 7th International Conference, FUN 2014, Lipari Island, Sicily, Italy, July 1-3, 2014. Proceedings　364-375　2014

DOI： 10.1007/978-3-319-07890-8_31 　
Minimum-cost b-edge dominating sets on trees Peer-reviewed

Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings　195-207　2014

DOI： 10.1007/978-3-319-13075-0_16 　
Fixed-parameter tractability of token jumping on planar graphs Peer-reviewed

Takehiro Ito, Marcin Kamiński, Hirotaka Ono

Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings　208-219　2014

DOI： 10.1007/978-3-319-13075-0_17 　
Polynomial-time algorithm for sliding tokens on trees Peer-reviewed

Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada

Algorithms and Computation - 25th International Symposium, ISAAC 2014, Jeonju, Korea, December 15-17, 2014, Proceedings　389-400　2014

DOI： 10.1007/978-3-319-13075-0_31 　
Reconfiguration of vertex covers in a graph Peer-reviewed

Takehiro Ito, Hiroyuki Nooka, Xiao Zhou

Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers　164-175　2014

DOI： 10.1007/978-3-319-19315-1_15 　
Deterministic algorithms for the independent feedback vertex set problem Peer-reviewed

Yuma Tamura, Takehiro Ito, Xiao Zhou

Combinatorial Algorithms - 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers　351-363　2014

DOI： 10.1007/978-3-319-19315-1_31 　
On the parameterized complexity for token jumping on graphs Peer-reviewed

Takehiro Ito, Marcin Kamiński, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, Katsuhisa Yamanaka

Theory and Applications of Models of Computation - 11th Annual Conference, TAMC 2014, Chennai, India, April 11-13, 2014. Proceedings　341-351　2014

DOI： 10.1007/978-3-319-06089-7_24 　
Route-enabling graph orientation problems Peer-reviewed

Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki, Ryuhei Uehara

Algorithmica　65　(2)　317-338　2013

DOI： 10.1007/s00453-011-9589-z 　
On the rainbow connectivity of graphs: Complexity and FPT algorithms Peer-reviewed

Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, Xiao Zhou

Algorithmica　67　(2)　161-179　2013

DOI： 10.1007/s00453-012-9689-4 　
On the minimum caterpillar problem in digraphs Peer-reviewed

Taku Okada, Akira Suzuki, Takehiro Ito, Xiao Zhou

Computing and Combinatorics, 19th International Conference, COCOON 2013, Hangzhou, China, June 21-23, 2013. Proceedings　729-736　2013

DOI： 10.1007/978-3-642-38768-5_66 　
Complexity of finding maximum regular induced subgraphs with prescribed degree Peer-reviewed

Yuichi Asahiro, Hiroshi Eto, Takehiro Ito, Eiji Miyano

Fundamentals of Computation Theory - 19th International Symposium, FCT 2013, Liverpool, UK, August 19-21, 2013. Proceedings　28-39　2013

DOI： 10.1007/978-3-642-40164-0_6 　
Base location problems for base-monotone regions Peer-reviewed

Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno

WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings　53-64　2013

DOI： 10.1007/978-3-642-36065-7_7 　
Generalized rainbow connectivity of graphs Peer-reviewed

Kei Uchizawa, Takanori Aoki, Takehiro Ito, Xiao Zhou

WALCOM: Algorithms and Computation, 7th International Workshop, WALCOM 2013, Kharagpur, India, February 14-16, 2013. Proceedings　233-244　2013

DOI： 10.1007/978-3-642-36065-7_22 　
Partitioning a weighted tree into subtrees with weights in a given range Peer-reviewed

Takehiro Ito, Takao Nishizeki, Michael Schröder, Takeaki Uno, Xiao Zhou

Algorithmica　62　(3月4日)　823-841　2012

DOI： 10.1007/s00453-010-9485-y 　
Minimum cost partitions of trees with supply and demand Peer-reviewed

Takehiro Ito, Takuya Hara, Xiao Zhou, Takao Nishizeki

Algorithmica　64　(3)　400-415　2012

DOI： 10.1007/s00453-011-9573-7 　
Reconfiguration of list edge-colorings in a graph Peer-reviewed

Takehiro Ito, Marcin Kamiński, Erik D. Demaine

Discrete Applied Mathematics　160　(15)　2199-2207　2012

DOI： 10.1016/j.dam.2012.05.014 　
An improved sufficient condition for reconfiguration of list edge-colorings in a tree Peer-reviewed

Takehiro Ito, Kazuto Kawamura, Xiao Zhou

IEICE Transactions　95-D　(3)　737-745　2012

DOI： 10.1587/transinf.E95.D.737 　
Packing trominoes is NP-complete, #P-complete and ASP-complete Peer-reviewed

Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, Ryuhei Uehara

Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG 2012, Charlottetown, Prince Edward Island, Canada, August 8-10, 2012　211-216　2012
Reconfiguration of list L(2, 1)-labelings in a graph Peer-reviewed

Takehiro Ito, Kazuto Kawamura, Hirotaka Ono, Xiao Zhou

Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings　34-43　2012

DOI： 10.1007/978-3-642-35261-4_7 　
A 4.31-approximation for the geometric unique coverage problem on unit disks Peer-reviewed

Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

Algorithms and Computation - 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012. Proceedings　372-381　2012

DOI： 10.1007/978-3-642-35261-4_40 　
A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares Peer-reviewed

Takehiro Ito, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno

Algorithm Theory - SWAT 2012 - 13th Scandinavian Symposium and Workshops, Helsinki, Finland, July 4-6, 2012. Proceedings　24-35　2012

DOI： 10.1007/978-3-642-31155-0_3 　
On disconnected cuts and separators Peer-reviewed

Takehiro Ito, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos

Discrete Applied Mathematics　159　(13)　1345-1351　2011

DOI： 10.1016/j.dam.2011.04.027 　
Minimum cost edge-colorings of trees can be reduced to matchings Peer-reviewed

Takehiro Ito, Naoki Sakamoto, Xiao Zhou, Takao Nishizeki

IEICE Transactions　94-D　(2)　190-195　2011

DOI： 10.1587/transinf.E94.D.190 　
On the complexity of reconfiguration problems Peer-reviewed

Takehiro Ito, Erik D. Demaine, Nicholas J, A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno

Theoretical Computer Science　412　(12-14)　1054-1065　2011

DOI： 10.1016/j.tcs.2010.12.005 　
Parameterizing cut sets in a graph by the number of their components Peer-reviewed

Takehiro Ito, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos

Theoretical Computer Science　412　(45)　6340-6350　2011

DOI： 10.1016/j.tcs.2011.07.005 　
On the rainbow connectivity of graphs: Complexity and FPT algorithms Peer-reviewed

Kei Uchizawa, Takanori Aoki, Takehiro Ito, Akira Suzuki, Xiao Zhou

Computing and Combinatorics - 17th Annual International Conference, COCOON 2011, Dallas, TX, USA, August 14-16, 2011. Proceedings　86-97　2011

DOI： 10.1007/978-3-642-22685-4_8 　
Approximability of the subset sum reconfiguration problem Peer-reviewed

Takehiro Ito, Erik D. Demaine

Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings　58-69　2011

DOI： 10.1007/978-3-642-20877-5_7 　
An improved sufficient condition for reconfiguration of list edge-colorings in a tree Peer-reviewed

Takehiro Ito, Kazuto Kawamura, Xiao Zhou

Theory and Applications of Models of Computation - 8th Annual Conference, TAMC 2011, Tokyo, Japan, May 23-25, 2011. Proceedings　94-105　2011

DOI： 10.1007/978-3-642-20877-5_10 　
Minimum cost edge-colorings of trees can be reduced to matchings Peer-reviewed

Takehiro Ito, Naoki Sakamoto, Xiao Zhou, Takao Nishizeki

Frontiers in Algorithmics, 4th International Workshop, FAW 2010, Wuhan, China, August 11-13, 2010. Proceedings　274-284　2010

DOI： 10.1007/978-3-642-14553-7_26 　
Minimum cost partitions of trees with supply and demand Peer-reviewed

Takehiro Ito, Takuya Hara, Xiao Zhou, Takao Nishizeki

Algorithms and Computation - 21st International Symposium, ISAAC 2010, Jeju Island, Korea, December 15-17, 2010, Proceedings, Part II　351-362　2010

DOI： 10.1007/978-3-642-17514-5_30 　
Partitioning graphs of supply and demand Peer-reviewed

Takehiro Ito, Xiao Zhou, Takao Nishizeki

Discrete Applied Mathematics　157　(12)　2620-2633　2009

DOI： 10.1016/j.dam.2008.08.012 　
A characterization of graphs with fractional total chromatic number equal to Delta+2 Peer-reviewed

Takehiro Ito, W. Sean Kennedy, Bruce A. Reed

Electronic Notes in Discrete Mathematics　35　235-240　2009

DOI： 10.1016/j.endm.2009.11.039 　
Route-enabling graph orientation problems Peer-reviewed

Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki, Ryuhei Uehara

Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings　403-412　2009

DOI： 10.1007/978-3-642-10631-6_42 　
Parameterizing cut sets in a graph by the number of their components Peer-reviewed

Takehiro Ito, Marcin Kamiński, Daniël Paulusma, Dimitrios M. Thilikos

Algorithms and Computation, 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings　605-615　2009

DOI： 10.1007/978-3-642-10631-6_62 　
Reconfiguration of list edge-colorings in a graph Peer-reviewed

Takehiro Ito, Marcin Kamiński, Erik D. Demaine

Algorithms and Data Structures, 11th International Symposium, WADS 2009, Banff, Canada, August 21-23, 2009. Proceedings　375-386　2009

DOI： 10.1007/978-3-642-03367-4_33 　
Approximability of partitioning graphs with supply and demand Peer-reviewed

Takehiro Ito, Erik D. Demaine, Xiao Zhou, Takao Nishizeki

Journal of Discrete Algorithms　6　(4)　627-650　2008

DOI： 10.1016/j.jda.2008.03.002 　
On the complexity of reconfiguration problems Peer-reviewed

Takehiro Ito, Erik D. Demaine, Nicholas J, A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, Yushi Uno

Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings　28-39　2008

DOI： 10.1007/978-3-540-92182-0_6 　
Partitioning a weighted tree to subtrees of almost uniform size Peer-reviewed

Takehiro Ito, Takeaki Uno, Xiao Zhou, Takao Nishizeki

Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15-17, 2008. Proceedings　196-207　2008

DOI： 10.1007/978-3-540-92182-0_20 　
Partitioning a multi-weighted graph to connected subgraphs of almost uniform size Peer-reviewed

Takehiro Ito, Kazuya Goto, Xiao Zhou, Takao Nishizeki

IEICE Transactions　90-D　(2)　449-456　2007

DOI： 10.1093/ietisy/e90-d.2.449 　
Algorithms for finding distance-edge-colorings of graphs Peer-reviewed

Takehiro Ito, Akira Kato, Xiao Zhou, Takao Nishizeki

Journal of Discrete Algorithms　5　(2)　304-322　2007

DOI： 10.1016/j.jda.2006.03.020 　
Partitioning a graph of bounded tree-width to connected subgraphs of almost uniform size Peer-reviewed

Takehiro Ito, Xiao Zhou, Takao Nishizeki

Journal of Discrete Algorithms　4　(1)　142-154　2006

DOI： 10.1016/j.jda.2005.01.005 　
Partitioning a multi-weighted graph to connected subgraphs of almost uniform size Peer-reviewed

Takehiro Ito, Kazuya Goto, Xiao Zhou, Takao Nishizeki

Computing and Combinatorics, 12th Annual International Conference, COCOON 2006, Taipei, Taiwan, August 15-18, 2006, Proceedings　63-72　2006

DOI： 10.1007/11809678_9 　
Approximability of partitioning graphs with supply and demand Peer-reviewed

Takehiro Ito, Erik D. Demaine, Xiao Zhou, Takao Nishizeki

Algorithms and Computation, 17th International Symposium, ISAAC 2006, Kolkata, India, December 18-20, 2006, Proceedings　121-130　2006

DOI： 10.1007/11940128_14 　
Partitioning trees of supply and demand Peer-reviewed

Takehiro Ito, Xiao Zhou, Takao Nishizeki

International Journal of Foundations of Computer Science　16　(4)　803-827　2005

DOI： 10.1142/S0129054105003303 　
Algorithms for finding distance-edge-colorings of graphs Peer-reviewed

Takehiro Ito, Akira Kato, Xiao Zhou, Takao Nishizeki

Computing and Combinatorics, 11th Annual International Conference, COCOON 2005, Kunming, China, August 16-29, 2005, Proceedings　798-807　2005

DOI： 10.1007/11533719_81 　
Partitioning graphs of supply and demand Peer-reviewed

Takehiro Ito, Xiao Zhou, Takao Nishizeki

International Symposium on Circuits and Systems (ISCAS 2005), 23-26 May 2005, Kobe, Japan　160-163　2005

DOI： 10.1109/ISCAS.2005.1464549 　
Partitioning a weighted graph to connected subgraphs of almost uniform size Peer-reviewed

Takehiro Ito, Xiao Zhou, Takao Nishizeki

Graph-Theoretic Concepts in Computer Science, 30th International Workshop, WG 2004, Bad Honnef, Germany, June 21-23, 2004, Revised Papers　365-376　2004

DOI： 10.1007/978-3-540-30559-0_31 　
Algorithms for multicolorings of partial k-trees Peer-reviewed

Takehiro Ito, Takao Nishizeki, Xiao Zhou

IEICE Transactions　E86-D　(2)　191-200　2003
Algorithms for the multicolorings of partial k-trees Peer-reviewed

Takehiro Ito, Takao Nishizeki, Xiao Zhou

Computing and Combinatorics, 8th Annual International Conference, COCOON 2002, Singapore, August 15-17, 2002, Proceedings　430-439　2002

DOI： 10.1007/3-540-45655-4_46 　
Partitioning trees of supply and demand Peer-reviewed

Takehiro Ito, Xiao Zhou, Takao Nishizeki

Algorithms and Computation, 13th International Symposium, ISAAC 2002 Vancouver, BC, Canada, November 21-23, 2002, Proceedings　612-623　2002

DOI： 10.1007/3-540-36136-7_53

Show all ︎Show first 5

Industrial Property Rights 6

配電系統制御装置

杉村修平, 田邊隆之, 周暁, 伊藤健洋, 鈴木顕

特許第7336359号

Property Type: Patent
配電系統制御装置

杉村修平, 田邊隆之, 周暁, 伊藤健洋, 鈴木顕, 畠山航

特許第7303500号

Property Type: Patent
配電系統制御装置

杉村修平, 田邊隆之, 周暁, 伊藤健洋, 鈴木顕, 千葉詩音

特許第7145109号

Property Type: Patent
配電自動化システムの電力融通方法

西関隆夫, 周暁, 伊藤健洋, 南部淳, 伊藤孝充, 田中哲司

特許第4622968号

Property Type: Patent
電力融通システム、電力融通方法、電力融通プログラム

伊藤健洋, 鈴木顕, 飯岡大輔, 川原純, 山岡宙太, 杉村修平, 田邊隆之, 後藤誠弥

Property Type: Patent
配電系統制御装置、配電系統制御方法

杉村修平, 田邊隆之, 伊藤健洋, 鈴木顕

Property Type: Patent

Show all Show first 5

Research Projects 20

Research on solvable regions of theoretically uncomputable/difficult classes

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (A)

Institution: Japan Advanced Institute of Science and Technology

2024/04 - 2029/03
解空間の形状に着目した組合せ遷移の理論：計算量解析の高精細化とソルバー新技法

伊藤健洋, 宋剛秀, 小林靖明, 野崎雄太

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 基盤研究(A)

Institution: 東北大学

2024/04 - 2028/03
迂回の特性を捉えた最短遷移アルゴリズムに関する研究

伊藤健洋

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 基盤研究(C)

Institution: 東北大学

2019/04/01 - 2025/03/31

More details Close

本年度は，Kempeら (2002年) が導入した時間ネットワークの概念において，その関連する遷移問題を研究した．この概念は，分散通信などネットワーク上の時間制約を解析するために導入され，時間ラベル付き有向グラフによって表現される．本研究では，時間制約付き有向全域木を対象とした遷移問題を解析した．これまでの研究に依って，時間制約の条件がない場合には，無向グラフであっても有向グラフであっても，任意の2つの全域木は互いに遷移可能であると知られている．すなわち，これら全域木からなる解空間グラフは常に連結である．加えて，無向・有向のいずれのグラフであっても，全域木の最短遷移問題も多項式時間で解けることが知られている．それとは対照的に，本研究では，時間制約を導入した場合には，解空間グラフは非連結となり得ることをまず示した．次に，そのような解空間グラフであっても，与えられた2つの時間制約付き有向全域木が互いに遷移可能であるかどうか（すなわち，到達判定）が，多項式時間で解けることを示した．その一方で，時間制約がある場合には最短遷移問題がNP困難であることを示し，時間制約の有無に依って計算複雑性が変わるという対比を示すことができた．本年度は他にも，グラフ上のラベル付きトークン遷移問題に関する研究も行った．この問題では多項式長の遷移系列の存在が示せるため，最短遷移問題が研究対象となる．この問題は，量子プログラムのコンパイラ設計に現れる量子ビットルーティング問題として，これまでも研究されてきた．既存研究では実践的なアプローチが主であったが，本研究では計算複雑性の理論的な解析に取り組み，NP困難性や特殊ケースにおける多項式時間アルゴリズム等を開発した．
Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration

ITO Takehiro

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Transformative Research Areas (B)

Institution: Tohoku University

2020/10/02 - 2023/03/31

More details Close

To facilitate smooth collaboration among researchers with backgrounds in computer science, engineering, and mathematics, and to widely publicize their research outcomes, we effectively managed this research project. To promote inter-group collaboration, we organized six project meetings, 35 seminars, and published five issues of newsletters. All of these activities were made publicly available. Additionally, we hosted numerous events across various fields. These included three co-located workshops at the international conference ICALP, four online one-day international workshops, two international programming competitions on combinatorial reconfiguration, two student symposia on combinatorial reconfiguration, and four outreach events.
Computer Science Approach for Expanding Combinatorial Reconfiguration: Toward Automatic Generation of Algorithms

ITO Takehiro

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Transformative Research Areas (B)

Institution: Tohoku University

2020/10/02 - 2023/03/31

More details Close

In this research, based in the field of computer science, we have published 73 peer-reviewed papers over a period of 3.5 years, including the carryover period. Through these studies, we were not only able to advance case studies of algorithms for various combinatorial reconfiguration problems, but we also succeeded in achieving our goal of establishing algorithmic meta-theorems for combinatorial reconfiguration. Additionally, we have made research advancements by incorporating enumeration and distributed computing methods from closely related fields into combinatorial reconfiguration. Furthermore, we have collaborated with other project groups and researchers from outside the project, enabling us to tackle various expansions in the algorithmic theory of combinatorial reconfiguration.
Research on algorithms and data structures for solving theoretically hard problems in practical time

Uehara Ryuhei

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (A)

Institution: Japan Advanced Institute of Science and Technology

2018/04/01 - 2023/03/31

More details Close

In recent decades, computational power has improved remarkably. However, contrary to what most users would imagine, the main factor behind the improvement in the speed at which computers solve problems is not the improvement in hardware performance, but the development of the software on top of it, especially algorithms and data structures, which has made a significant contribution. In this research theme, we first demonstrated the theoretical difficulty of various combinatorial optimization problems, and then used the problem properties revealed in the process to design and develop algorithms for solving the problems efficiently.
Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Transformative Research Areas (B)

2020/10 - 2023/03
Development of Algorithmic Techniques for Combinatorial Reconfiguration

Offer Organization: Japan Society for the Promotion of Science

System: Bilateral Collaborations

2018/04 - 2020/03
Algorithms and their generalizations for vehicle routing problems of minimizing regrets

ITO Takehiro

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (C)

Institution: Tohoku University

2016/04/01 - 2019/03/31

More details Close

We studied a recently proposed variant of vehicle routing problems which takes the customers’ regrets as the objective function. We developed algorithms for the problem using structures of input graphs, and also proved some computational hardness and inapproximability. In addition, we introduced some generalized variant, and examined an extension of our algorithms in order to put our developed methods in place. Our approximation method for trees is best possible from the viewpoint of approximation ratio, because one can choose an arbitrarily better ratio.
解空間のパラメータ化解析による計算困難性と容易性の解明

伊藤健洋

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 新学術領域研究(研究領域提案型)

Institution: 東北大学

2015/04/01 - 2017/03/31

More details Close

本年度は，シュタイナー木の遷移問題について，その計算困難性と容易性を解析した．特に，スプリットグラフでは計算困難であるが，区間グラフでは計算容易であることを示しており，グラフ構造の観点から興味深い対比を与えている．すなわち，スプリットグラフはクリークが木（スター）構造を成しているグラフであり，区間グラフはクリークがパス構造を成しているグラフである．どちらのグラフも辺が密であり，比較的近い構造を持つが，その計算複雑さに差があることを示した．また，（リスト）辺彩色の遷移問題について，その計算困難性を示した．辺ごとに使用可能な色が限定されない辺彩色の遷移問題については，その計算困難性が一切知られていなかったが，本研究では初めて計算困難性を示すことに成功した．辺ごとに使用可能な色集合が与えられるリスト辺彩色の遷移問題は，従来研究では，彩色に使用できる色数が３色以下であれば計算容易であり，６色以上であれば計算困難であることが知られていた．すなわち，色数が４色と５色の場合は未解決であったが，本研究では，どちらも計算困難であることを証明した．これにより，色数に基づく計算困難性と容易性を完全に特徴づけることに成功した．これら（リスト）辺彩色の遷移問題に関する計算困難性の証明は，遷移問題における帰着手法の特徴を与えることで達成している．すなわち，帰着を構成する際に，解空間の連結性を「内部連結」と「外部連結」という二つの概念を用いて保証した．これにより，複雑な帰着の正当性を計算機によって検証することを可能とした．実際，本研究で与えた証明では，可能な辺彩色が約３０万種類もあり，計算機による検証なしでは証明は難しかったであろう．
Development of algorithms for the server-assignment problem to maximize available capacity of networks

ITO TAKEHIRO

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (C)

Institution: Tohoku University

2013/04/01 - 2016/03/31

More details Close

We modeled the following situation as a graph problem: In a network, we wish to find a way of data distributions from servers to all users to avoid any congestion of network links. We studied the complexity status of this problem from the viewpoint of graph structures, and clarified how the complexity status depends on the number of cycles or the number of servers in a graph. In many cases, this problem is computationally intractable, and hence we gave pseudo-polynomial-time algorithms based on a dynamic programming method and fixed-parameter algorithms.
解空間の直径に基づく計算限界解析アプローチの構築

伊藤健洋

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 新学術領域研究(研究領域提案型)

Institution: 東北大学

2013/04/01 - 2015/03/31

More details Close

本年度は，点彩色を一般化した「リスト点彩色」の遷移問題に対して，詳細な解析を与えることができた．グラフ構造の指標として「パス幅」と呼ばれるパラメータがあるが，パス幅が2以上であればリスト点彩色の遷移問題はPSPACE完全であり，パス幅が1であれば多項式時間で解けることを示した．すなわち，これはリスト点彩色の遷移問題の計算困難性と容易性を，入力グラフのパス幅の観点から特徴づけたことになる．パス幅1の入力グラフに対する多項式時間アルゴリズムは動的計画法に基づいており，遷移問題に対して動的計画法を適用した例としても評価できる． <br> また，独立点集合の遷移問題に対しては，固定パラメータ容易性（FPT）の観点から，研究を進めることができた．この問題は，平面グラフにおいてPSPACE完全であることが示されており，解空間グラフの直径は超多項式長になる．しかし本研究では，独立点集合のサイズのみをパラメータとして，平面グラフに対するFPTアルゴリズムを与えた．この研究成果により，解空間グラフの直径が超多項式長になることを単に示すだけでなく，パラメータにどのように依存するのか解析することができた．特に，本研究では昨年度，一般のグラフに対しては，独立点集合のサイズのみをパラメータとしたFPTアルゴリズムを持ちそうにないことを証明しており，今年度の研究と対比させることで，入力グラフの構造と計算困難性の関係をより具体的に解析することができた． <br> この他にも，点彩色と関連が深いL(2,1)ラベリングなど，様々な遷移問題に対してアルゴリズムを開発することで，解空間グラフの直径が多項式長で抑えられる場合を明らかにし，計算困難である場合との対比を可能とした．特に，本研究では，入力グラフの構造を上手く利用することで，効率のよいアルゴリズムを多数開発することができた．
Efficient Algorithms for Partitionings, Colorings and Drawings of Graphs and their Applications

NISHIZEKI Takao, ZHOU Xiao, ITO Takehiro, UCHIZAWA Kei

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (C)

2009/04/01 - 2014/03/31

More details Close

This research develops efficient algorithms for the partitioning, coloring and drawing problems of graphs, and applies them to practical problems in real world. One of the representative results is an algorithm for the fairest connected partition problem. It partitions a weighted graph G to a specified number of connected subgraphs by deleting edges from G so that the difference between the maximum sum of weights in a subgraph and the minimum one is as small as possible.
A Study of Reconfiguration Problems to Develop Dynamic Systems

ITO Takehiro

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Young Scientists (B)

Institution: Tohoku University

2010 - 2012

More details Close

In this research, we study problems of finding a step-by-step transformation between two feasible solutions of a problem such that all intermediate results are also feasible. In particular, we study such problems for knapsack problem, which is one of the most fundamental problems in theoretical computer science, and for graph partitioning problem with supply and demand, which has some applications to power delivery network. We first analyzed the computational hardness of these problems, and then gave approximationalgorithms. Our approximation algorithms are best possible from the viewpoint of approximation ratio.
Heuristic algorithms with reasonable running time

ITO Takehiro

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Young Scientists (B)

Institution: Tohoku University

2008 - 2009

More details Close

In this research, we obtained heuristic algorithms which runs in reasonable time from the viewpoint of practical applications. We dealt with two graph partition problems, called the power-supply problem and the uniform partition problem. For the power-supply problem, we gave an approximation algorithm, called an FPTAS. Based on the FPTAS, we also gave a heuristic algorithm. For the uniform partition problem, we gave a polynomial-time algorithm which finds an optimal solution for trees.
Graph Drawing Algorithms and Applications to VLSI Designs

NISHIZEKI Takao, XIAO Zhou, ITO Takehiro, UCHIZAWA Kei

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (C)

Institution: Tohoku University

2007 - 2008
グラフ分割アルゴリズムの新しい設計手法に関する研究

伊藤健洋

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 若手研究(スタートアップ)

Institution: 東北大学

2006 - 2007

More details Close

本年度は,主に選挙区割問題などに応用がある「グラフの均一分割問題」について研究を行った.この問題は,点に整数の重みが付いたグラフが与えられたとき,グラフから辺を削除し,各連結成分に含まれる点の重みの合計が均一になるように分割する問題である.本研究では,各点に2つ以上の重みが与えられていても,部分k木の均一分割問題が擬多項式時間で解けることを示した.また,2つ以上与えられた点の重みのうち,分割を求める際には1つだけを自由に選択できる場合についても考察を行い,擬多項式時間アルゴリズムを与えることができた.これらの結果は,IEICE Trans.on Information and Systemsに掲載になった. また,電力系統の配電融通問題などに応用がある「需要点と供給点のあるグラフの分割問題」も研究を進めた.この問題は,需要点と供給点のあるグラフに対し,電力が供給されない需要点ができてしまうとき,供給されている需要点の需要量の合計を最大にする最大化問題である.この問題の近似可能性を明らかにした論文を,海外の学術雑誌に投稿した.
グラフ描画アルゴリズムとそのWeb情報検索への応用

西関隆夫, 周暁, 伊藤健洋, 三浦一之, 浅野泰仁

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 特定領域研究

Institution: 東北大学

2004 - 2007

More details Close

(1)平面的グラフの折れ曲がりなし直交描画問題について,グラフが3連結立方グラフの細分であれば,折れ曲がりなし直交描画を線形時間で求めることのできるアルゴリズムを与えた. (2)直並列グラフの直交描画で折れ曲り数最少のものを求める線形アルゴリズムを開発した. (3)平面グラフの格子凸描画において,別個に研究されてきた標準分解,リアライザ,シュナイダーラベリング,順序つき全域木がすべて同等であることを証明した. (4)VLSIレイアウトに平面グラフの内部矩形描画が応用できる.与えられた平面グラフが内部矩形描画できるかどうか判定し,できるならば内部矩形描画を高速に求めるアルゴリズムを与えた. (5)電力供給問題のモデル化であり,一般には強NP困難問題として知られる,需要・供給付きグラフの分割問題について研究し,分割数を最少・最多にする問題,および指定された個数の連結成分への分割を求める問題に対して,グラフが木(または部分k-木)であるときに厳密解を求める多項式時間(または擬似多項式時間)アルゴリズムを与えた. (6)購入した計算機を用いてウェブ文書データを解析し,サイトのデータを抽出し,このデータからサイトを点とするサイト間グラフを構築した.さらに,サイト間グラフの特徴を利用して,著名な情報検索手法であるmax-flow based methodの品質を大幅に改善する手法を確立し,実験によってその性能を検証した.
Unified Methodology for Designing Efficient Algorithms

NISHIZEKI Takao, ZHOU Xiao, ITO Takehiro

Offer Organization: Japan Society for the Promotion of Science

System: Grants-in-Aid for Scientific Research

Category: Grant-in-Aid for Scientific Research (C)

Institution: Tohoku University

2005 - 2006

More details Close

In this project, we consider the coloring problem, the disjoint path problem and the drawing problem for structured graphs such as trees, series-parallel graphs and partial k-trees, and succeeded in obtaining efficient algorithms for these classes of graphs. We also establish the foundation for the unified methodology of designing efficient algorithms for structured graphs. For trees, we obtain a fully polynomial-time approximation scheme (FPTAS) for the partitioning problem of trees having supply and demand. For series-parallel graphs, we first obtain a sufficient condition for the existence of a list total coloring, and then give a linear-time algorithm to find a list total coloring. For partial k-trees, we succeeded in obtaining three algorithms : the first is a linear-time algorithm for the total coloring problem ; the second is a pseudo-polynomial-time algorithm for the uniform partitioning problem ; and the third is a pseudo-polynomial-time algorithm for the partitioning problem on graphs with supply and demand. Concerning graph drawing, we obtain a linear-time algorithm to find an orthogonal drawing of series-parallel graphs with the minimum number of bends, and give a graph decomposition applicable to a convex drawing. In conclusion, we succeeded in designing efficient algorithms for various problems, and laid the foundation of unified methodology to design efficient algorithms for combinatorial problems, especially for the partition problems to edge-disjoint subgraphs. These results are published in seven journal papers and five proceedings papers of international conferences.
グラフの多重彩色及び分割に関するアルゴリズム

伊藤健洋

Offer Organization: 日本学術振興会

System: 科学研究費助成事業

Category: 特別研究員奨励費

Institution: 東北大学

2003 - 2005

More details Close

本研究では,グラフの点に供給点または需要点の役割が与えられ,それぞれに供給量と需要量という重みが与えられた重み付きグラフを扱った.そのようなグラフに対し,需要と供給の条件を満たすようにグラフを分割するアルゴリズムを開発した. まず,木のグラフ分割問題に関してまとめた論文が,学術雑誌に採録された. 次に,直並列グラフと呼ばれるグラフのクラスに対し,グラフ分割問題を解くアルゴリズムの開発・解析を行った.グラフ分割問題は木に対してさえNP困難であり,したがって直並列グラフに対し効率のよいアルゴリズムはありそうにない.そこで,本研究では擬多項式時間アルゴリズムの開発を行った.その結果は,2005年5月開催の国際会議にて発表し,現在学術雑誌に投稿中である. また,直並列グラフに対し,より一般的な分割問題を解くアルゴリズムを与えた.この問題では,今まで上限のみ指定することができた連結成分の重みの和の制限を,上限と下限の両方を同時に指定することができるようにした.さらに,グラフの点に複数個の重みが割当てられている場合にも,効率よく解けることを示した.この結果は,現在国際会議に投稿するように準備中である.

Show all Show first 5