教養学士, 東京大学, Mar. 1999

修士（学術）, 東京大学, Mar. 2001

Ph.D., ETH Zurich, Mar. 2005

Discrete Algorithms

Discrete Optimization

Discrete Mathematics

Discrete and Computational Geometry

Graph Algorithms

Combinatorial Reconfiguration

Algorithmic Game Theory

Informatics, Information theory

Informatics, Mathematical informatics

Natural sciences, Basic mathematics

Natural sciences, Applied mathematics and statistics

Social infrastructure (civil Engineering, architecture, disaster prevention), Social systems engineering

Social infrastructure (civil Engineering, architecture, disaster prevention), Safety engineering

01 Apr. 2017
電気通信大学, 大学院情報理工学研究科 情報・ネットワーク工学専攻, 教授

01 Apr. 2016 - 31 Mar. 2017
電気通信大学, 大学院情報理工学研究科 情報・ネットワーク工学専攻, 准教授

01 Apr. 2012 - 31 Mar. 2016
電気通信大学, 大学院情報理工学研究科 情報・通信工学専攻, 准教授

01 Oct. 2010 - 31 Mar. 2012
北陸先端科学技術大学院大学, 大学院教育イニシアティブセンター, 特任准教授

01 Dec. 2007 - 30 Sep. 2010
東京工業大学, 大学院情報理工学研究科, 特任准教授

01 Apr. 2007 - 30 Nov. 2007
豊橋技術科学大学, 工学部 情報工学系, 助教

01 Apr. 2005 - 31 Mar. 2007
豊橋技術科学大学, 工学部 情報工学系, 助手

Apr. 2002 - Mar. 2005
ETH Zurich, Department of Computer Science, Switzerland

Apr. 1999 - Mar. 2001
The University of Tokyo, Graduate School of Arts and Sciences, Department of General Systems Studies

Apr. 1995 - Mar. 1999
The University of Tokyo, College of Arts and Sciences, Department of Systems Science

Apr. 1992 - Mar. 1995
岡崎高等学校, 普通科

Jun. 2025
Outstanding Reviewer Award of SoCG 2025, Yoshio Okamoto
International society

Jan. 2024
情報処理学会
2023年度コンピュータサイエンス領域功績賞, 岡本吉央
Japan society

Mar. 2022
日本オペレーションズ・リサーチ学会
日本オペレーションズ・リサーチ学会フェロー

Sep. 2021
船井ベストペーパー賞, 岡本吉央;伊藤健洋;垣村尚徳;神山直之;小林佑輔
Japan society

Sep. 2020
日本オペレーションズ・リサーチ学会
日本オペレーションズ・リサーチ学会第10回研究賞
Japan society

2015
日本ソフトウェア科学会
日本ソフトウェア科学会第5回解説論文賞, 横尾真;岩崎敦;櫻井祐子;岡本吉央
Japan society

2012
日本オペレーションズ・リサーチ学会
日本オペレーションズ・リサーチ学会研究賞奨励賞

2010
EATCS, LA Symposium
8th EATCS/LA Presentation Award

2004
Editors' Choice 2003, Discrete Applied Mathematics

The Solitaire Clobber game and the correducibility of k-connected graphs
Tatsuya Fujimori; Shun-ichi Maezawa; Yoshio Okamoto
Discrete Applied Mathematics, Elsevier BV, 366, 16-22, May 2025, Peer-reviwed
Scientific journal

Reforming an Envy-Free Matching
Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
Algorithmica, 87, 4, 594-620, Apr. 2025, Peer-reviwed
Scientific journal

Reconfiguration of colorings in triangulations of the sphere
Takehiro Ito; Yuni Iwamasa; Yusuke Kobayashi; Shun-ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
Journal of Computational Geometry, 16, 1, 253-294, Apr. 2025, Peer-reviwed, True
Scientific journal, English

Rerouting Planar Curves and Disjoint Paths
Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Yusuke Kobayashi; Shun-Ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
ACM Transactions on Algorithms, 21, 2, 1-37, Mar. 2025, Peer-reviwed
Scientific journal

Minimum separator reconfiguration
Guilherme C.M. Gomes; Clément Legrand-Duchesne; Reem Mahmoud; Amer E. Mouawad; Yoshio Okamoto; Vinicius F. dos Santos; Tom C. van der Zanden
Journal of Computer and System Sciences, Elsevier BV, 146, 103574-103574, Dec. 2024, Peer-reviwed, True, with international co-author(s)
Scientific journal

CoRe Challenge 2022/2023: Empirical Evaluations for Independent Set Reconfiguration Problems (Extended Abstract)
Takehide Soh; Tomoya Tanjo; Yoshio Okamoto; Takehiro Ito
Proceedings of the 17th International Symposium on Combinatorial Search (SOCS 2024), Association for the Advancement of Artificial Intelligence (AAAI), 17, 285-286, 01 Jun. 2024, Peer-reviwed, True
International conference proceedings

Minimum Separator Reconfiguration
Guilherme C. M. Gomes; Clément Legrand-Duchesne; Reem Mahmoud; Amer E. Mouawad; Yoshio Okamoto; Vinícius Fernandes dos Santos; Tom C. van; der Zanden
18th International Symposium on Parameterized and Exact Computation (IPEC 2023), 9:1-9:12, Dec. 2023, Peer-reviwed
International conference proceedings

On reachable assignments under dichotomous preferences
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
Theoretical Computer Science, Elsevier BV, 979, 114196-114196, Nov. 2023, Peer-reviwed
Scientific journal

Algorithmic Theory of Qubit Routing
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
WADS, 533-546, Jul. 2023, Peer-reviwed
International conference proceedings

Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Shun-ichi Maezawa; Yuta Nozaki; Yoshio Okamoto
ICALP, 82-17, Jul. 2023, Peer-reviwed
International conference proceedings

Rerouting Planar Curves and Disjoint Paths
Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Yusuke Kobayashi; Shun-ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
ICALP, 81-19, Jul. 2023, Peer-reviwed
International conference proceedings

Reconfiguration of Colorings in Triangulations of the Sphere
Takehiro Ito; Yuni Iwamasa; Yusuke Kobayashi; Shun-ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
SoCG, 43-16, Jun. 2023, Peer-reviwed
International conference proceedings

Algorithmic Theory of Qubit Routing
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
CoRR, abs/2305.02059, May 2023
Scientific journal

Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Shun-ichi Maezawa; Yuta Nozaki; Yoshio Okamoto
CoRR, abs/2304.14782, Apr. 2023
Scientific journal

Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams
Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Shun-Ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
ACM Transactions on Algorithms, Association for Computing Machinery (ACM), 19, 1, 1-22, 31 Jan. 2023, Peer-reviwed
Scientific journal

Graphs with large total angular resolution
Oswin Aichholzer; Matias Korman; Yoshio Okamoto; Irene Parada; Daniel Perz; André van Renssen; Birgit Vogtenhuber
Theoretical Computer Science, Elsevier BV, 943, 73-88, Jan. 2023, Peer-reviwed
Scientific journal

On Reachable Assignments Under Dichotomous Preferences
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
PRIMA 2022: Principles and Practice of Multi-Agent Systems, Springer International Publishing, 650-658, Nov. 2022, Peer-reviwed
In book

Rerouting Planar Curves and Disjoint Paths
Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Yusuke Kobayashi; Shun-ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
CoRR, abs/2210.11778, Oct. 2022
Scientific journal

Core Challenge 2022: Solver and Graph Descriptions
Takehide Soh; Yoshio Okamoto; Takehiro Ito
CoRR, abs/2208.02495, Aug. 2022
Scientific journal

Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
Bahareh Banyassady; Mark de Berg; Karl Bringmann; Kevin Buchin; Henning Fernau; Dan Halperin; Irina Kostitsyna; Yoshio Okamoto; Stijn Slot
Proceedings of 38th International Symposium on Computational Geometry (SoCG 2022), 12:1-12:16, Jun. 2022, Peer-reviwed
International conference proceedings, English

Weight balancing on boundaries
Luis Barba; Otfried Cheong; Michael Gene Dobbins; Rudolf Fleischer; Akitoshi Kawamura; Matias Korman; Yoshio Okamoto; Janos Pach; Yuan Tang; Takeshi Tokuyama; Sander Verdonschot
Journal of Computational Geometry, 13, 1, 1-12, Jun. 2022, Peer-reviwed, with international co-author(s)
English

Reforming an Envy-Free Matching
Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
AAAI, 5084-5091, Jun. 2022, Peer-reviwed
International conference proceedings

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
SIAM Journal on Discrete Mathematics, Society for Industrial & Applied Mathematics (SIAM), 36, 2, 1102-1123, Jun. 2022, Peer-reviwed
Scientific journal

A Parameterized View to the Robust Recoverable Base Problem of Matroids Under Structural Uncertainty
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
Operations Research Letters, Elsevier BV, May 2022, Peer-reviwed
Scientific journal

Linear-Time Recognition of Double-Threshold Graphs.
Yusuke Kobayashi 0001; Yoshio Okamoto; Yota Otachi; Yushi Uno
Algorithmica, 84, 4, 1163-1181, 2022
Scientific journal

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams
Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Shun-ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
SODA, 1342-1355, Jan. 2022, Peer-reviwed
International conference proceedings

Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams
Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Shun-ichi Maezawa; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
CoRR, abs/2110.11585, Oct. 2021
Scientific journal

Submodular reassignment problem for reallocating agents to tasks with synergy effects
Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
Discrete Optimization, Elsevier BV, 100631-100631, Feb. 2021, Peer-reviwed
Scientific journal

ClusterSets: Optimizing planar clusters in categorical point data
Jakob Geiger; Sabine Cornelsen; Jan-Henrik Haunert; Philipp Kindermann; Tamara Mchedlidze; Martin Nöllenburg; Yoshio Okamoto; Alexander Wolff
Proceedings of 23rd EG Conference on Visualization (EuroVis 2021), Computer Graphics Forum, 40, 471-481, 2021, Peer-reviwed
International conference proceedings, English

Algorithms for gerrymandering over graphs.
Takehiro Ito; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto
Theor. Comput. Sci., 868, 30-45, 2021, Peer-reviwed
Scientific journal

Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain
Elena Arseneva; Man-Kwun Chiu; Matias Korman; Aleksandar Markovic; Yoshio Okamoto; Aurélien Ooms; André van Renssen; Marcel Roeloffzen
Computational Geometry: Theory and Applications, 92, 58:1-58:13, 2021, Peer-reviwed
Scientific journal, English

Algorithmic enumeration of surrounding polygons
Katsuhisa Yamanaka; David Avis; Takashi Horiyama; Yoshio Okamoto; Ryuhei Uehara; Tanami Yamauchi
Discrete Applied Mathematics, Elsevier BV, Apr. 2020, Peer-reviwed
Scientific journal

Balanced line separators of unit disk graphs
Paz Carmi; Man Kwun Chiu; Matthew J. Katz; Matias Korman; Yoshio Okamoto; André van Renssen; Marcel Roeloffzen; Taichi Shiitada; Shakhar Smorodinsky
Computational Geometry: Theory and Applications, Elsevier B.V., 86, 01 Jan. 2020
Scientific journal, English

Linear-Time Recognition of Double-Threshold Graphs
Yusuke Kobayashi; Yoshio Okamoto; Yota Otachi; Yushi Uno
Proceedings of 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020), Springer, 286-297, 2020, Peer-reviwed
International conference proceedings, English

Subgraph Isomorphism on Graph Classes that Exclude a Substructure.
Hans L. Bodlaender; Tesshu Hanaka; Yoshio Okamoto; Yota Otachi; Tom C. van der Zanden
Algorithms and Complexity - 11th International Conference(CIAC), Springer, 82, 12, 87-98, 2019, Peer-reviwed
International conference proceedings, English

Graphs with Large Total Angular Resolution
Oswin Aichholzer; Matias Korman; Yoshio Okamoto; Irene Parada; Daniel Perz; André van Renssen; Birgit Vogtenhuber
Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019), 193-199, 2019, Peer-reviwed
International conference proceedings, English

Variants of the Segment Number of a Graph
Yoshio Okamoto; Alexander Ravsky; Alexander Wolff
Proceedings of 27th International Symposium on Graph Drawing and Network Visualization (GD 2019), 430-443, 2019, Peer-reviwed
International conference proceedings, English

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles.
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto
27th Annual European Symposium on Algorithms(ESA), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 61-15, 2019, Peer-reviwed
International conference proceedings

Computing the Geodesic Centers of a Polygonal Domain
Sang Won Bae; Matias Korman; Yoshio Okamoto
Computational Geometry: Theory and Applications, 77, 3-9, 2019, Peer-reviwed
Scientific journal, English

Minimum-Cost b-Edge Dominating Sets on Trees.
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto
Algorithmica, 81, 1, 343-366, 2019, Peer-reviwed
Scientific journal, English

Sequentially Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka; Erik D. Demaine; Takashi Horiyama; Akitoshi Kawamura; Shin-Ichi Nakano; Yoshio Okamoto; Toshiki Saitoh; Akira Suzuki; Ryuhei Uehara; Takeaki Uno
Journal of Graph Algorithms and Applications, 23, 1, 3-27, 2019, Peer-reviwed
Scientific journal, English

Reconfiguration of maximum-weight b-matchings in a graph.
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto
J. Comb. Optim., 37, 2, 454-464, 2019, Peer-reviwed
Scientific journal, English

Area bounds of rectilinear polygons realized by angle sequences
Sang Won Bae; Yoshio Okamoto; Chan-Su Shin
Computational Geometry: Theory and Applications, 83, 9-29, 2019, Peer-reviwed
Scientific journal, English

Algorithms for Gerrymandering over Graphs.
Takehiro Ito; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto
Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), International Foundation for Autonomous Agents and Multiagent Systems, 1413-1421, 2019, Peer-reviwed
International conference proceedings, English

Shortest Reconfiguration of Perfect Matchings via Alternating Cycles.
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto
CoRR, abs/1907.01700, 61:1-61:15, 2019, Peer-reviwed
Scientific journal, English

Tight Approximability of the Server Allocation Problem for Real-Time Applications
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto; Taichi Shiitada
Algorithmic Aspects of Cloud Computing, Springer International Publishing, 41-55, 2018, Peer-reviwed
In book, English

Exact Algorithms for the Max-Min Dispersion Problem.
Toshihiro Akagi; Tetsuya Araki; Takashi Horiyama; Shin-Ichi Nakano; Yoshio Okamoto; Yota Otachi; Toshiki Saitoh; Ryuhei Uehara; Takeaki Uno; Kunihiro Wasa
Proceedings of 12th International Frontiers of Algorithmics Workshop (FAW 2018), Springer, 263-272, 2018, Peer-reviwed
International conference proceedings, English

Computational Complexity of Robot Arm Simulation Problems
Tianfeng Feng; Takashi Horiyama; Yoshio Okamoto; Yota Otachi; Toshiki Saitoh; Takeaki Uno; Ryuhei Uehara
Proceedings of 29th International Workshop on Combinational Algorithms (IWOCA 2018), Springer, 177-188, 2018, Peer-reviwed
International conference proceedings, English

Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity
Evmorfia Argyriou; Sabine Cornelsen; Henry Förster; Michael Kaufmann; Martin Nöllenburg; Yoshio Okamoto; Chrysanthi Raftopoulou; Alexander Wolff
Proceedings of 26th International Symposium on Graph Drawing and Network Visualization (GD 2018), 509-523, 2018, Peer-reviwed
International conference proceedings, English

Folding free-space diagrams: Computing the Fréchet distance between 1-dimensional curves
Kevin Buchin; Jinhee Chun; Maarten Löffler; Aleksandar Markovic; Wouter Meulemans; Yoshio Okamoto; Taichi Shiitada
Leibniz International Proceedings in Informatics, LIPIcs, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 77, 641-645, 01 Jun. 2017, Peer-reviwed
International conference proceedings, English

Efficient stabilization of cooperative matching games
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
THEORETICAL COMPUTER SCIENCE, 677, 69-82, May 2017, Peer-reviwed
Scientific journal, English

Computing the L-1 Geodesic Diameter and Center of a Polygonal Domain
Sang Won Bae; Matias Korman; Joseph S. B. Mitchell; Yoshio Okamoto; Valentin Polishchuk; Haitao Wang
DISCRETE & COMPUTATIONAL GEOMETRY, 57, 3, 674-701, Apr. 2017, Peer-reviwed
Scientific journal, English

General Constructions of Rational Secret Sharing with Expected Constant-Round Reconstruction
Akinori Kawachi; Yoshio Okamoto; Keisuke Tanaka; Kenji Yasunaga
COMPUTER JOURNAL, 60, 5, 711-728, Apr. 2017, Peer-reviwed
Scientific journal, English

Sequentially Swapping Colored Tokens on Graphs
Katsuhisa Yamanaka; Erik D. Demaine; Takashi Horiyama; Akitoshi Kawamura; Shin-ichi Nakano; Yoshio Okamoto; Toshiki Saitoh; Akira Suzuki; Ryuhei Uehara; Takeaki Uno
WALCOM: ALGORITHMS AND COMPUTATION, WALCOM 2017, 10167, 435-447, 2017, Peer-reviwed
International conference proceedings, English

Sankaku-Tori: An Old Western-Japanese Game Played on a Point Set
Takashi Horiyama; Takashi Iizuka; Masashi Kiyomi; Yoshio Okamoto; Ryuhei Uehara; Takeaki Uno; Yushi Uno; Yukiko Yamauchi
Journal of Information Processing, 25, 8, 708-715, 2017, Peer-reviwed
Scientific journal, English

Balanced line separators of unit disk graphs
Paz Carmi; Man Kwun Chiu; Matthew J. Katz; Matias Korman; Yoshio Okamoto; André Van Renssen; Marcel Roeloffzen; Taichi Shiitada; Shakhar Smorodinsky
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 10389, 241-252, 2017, Peer-reviwed
International conference proceedings, English

Reconfiguration of maximum-weight b-matchings in a graph
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Springer Verlag, 10392, 287-296, 2017, Peer-reviwed
International conference proceedings, English

Extended formulations for sparsity matroids
Satoru Iwata; Naoyuki Kamiyama; Naoki Katoh; Shuji Kijima; Yoshio Okamoto
MATHEMATICAL PROGRAMMING, 158, 1-2, 565-574, Jul. 2016, Peer-reviwed
Scientific journal, English

Computational Complexity of Sequential Token Swapping Problem (コンピュテーション)
山中 克久; ドメイン エリック; 堀山 貴史; 河村 彰星; 中野 眞一; 岡本 吉央; 斎藤 寿樹; 鈴木 顕; 上原 隆平; 宇野 毅明
電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 電子情報通信学会, 116, 116, 115-121, 24 Jun. 2016
English

シーケンシャルな交換による色付きトークン整列問題の計算複雑さ
山中 克久; エリック ドメイン; 堀山 貴史; 河村 彰星; 中野 眞一; 岡本 吉央; 斎藤 寿樹; 鈴木 顕; 上原 隆平; 宇野 毅明
第158回アルゴリズム研究会, 1-7, Jun. 2016
Symposium, Japanese

On Problems as Hard as CNF-SAT
Marek Cygan; Holger Dell; Daniel Lokshtanov; Daniel Marx; Jesper Nederlof; Yoshio Okamoto; Ramamohan Paturi; Saket Saurabh; Magnus Wahlstrom
ACM TRANSACTIONS ON ALGORITHMS, 12, 3, Jun. 2016, Peer-reviwed
Scientific journal, English

A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
Takehiro Ito; Shin-ichi Nakano; Yoshio Okamoto; Yota Otachi; Ryuhei Uehara; Takeaki Uno; Yushi Uno
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 51, 25-39, Jan. 2016, Peer-reviwed
Scientific journal, English

On the treewidth of toroidal grids
Masashi Kiyomi; Yoshio Okamoto; Yota Otachi
DISCRETE APPLIED MATHEMATICS, 198, 303-306, Jan. 2016, Peer-reviwed
Scientific journal, English

Efficient Stabilization of Cooperative Matching Games
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
Proceedings of 15th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2016), 41-49, 2016, Peer-reviwed
International conference proceedings, English

Approximation and Hardness of Token Swapping
Tillmann Miltzow; Lothar Narins; Yoshio Okamoto; Günter Rote; Antonis Thomas; Takeaki Uno
Proceedings of 24th European Symposium on Algorithms (ESA 2016), 66:1-66:15, 2016, Peer-reviwed
International conference proceedings, English

Computing the L-1 geodesic diameter and center of a simple polygon in linear time
Sang Won Bae; Matias Korman; Yoshio Okamoto; Haitao Wang
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 48, 6, 495-505, Aug. 2015, Peer-reviwed
Scientific journal, English

Free Edge Lengths in Plane Graphs
Zachary Abel; Robert Connelly; Sarah Eisenstat; Radoslav Fulek; Filip Moric; Yoshio Okamoto; Tibor Szabo; Csaba D. Toth
DISCRETE & COMPUTATIONAL GEOMETRY, 54, 1, 259-289, Jul. 2015, Peer-reviwed
Scientific journal, English

Swapping labeled tokens on graphs
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, Jun. 2015, Peer-reviwed
Scientific journal, English

Polynomial-time approximability of the k-Sink Location problem.
Rémy Belmonte; Yuya Higashikawa; Naoki Katoh; Yoshio Okamoto
CoRR, abs/1503.02835, 2015

A 4.31-approximation for the geometric unique coverage problem on unit disks
Takehiro Ito; Shin-ichi Nakano; Yoshio Okamoto; Yota Otachi; Ryuhei Uehara; Takeaki Uno; Yushi Uno
THEORETICAL COMPUTER SCIENCE, 544, 14-31, Aug. 2014, Peer-reviwed
Scientific journal, English

Computational Complexity and an Integer Programming Model of Shakashaka
Erik D. Demaine; Yoshio Okamoto; Ryuhei Uehara; Yushi Uno
IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, E97A, 6, 1213-1219, Jun. 2014, Peer-reviwed
Scientific journal, English

Submodularity of minimum-cost spanning tree games
Masayuki Kobayashi; Yoshio Okamoto
NETWORKS, 63, 3, 231-238, May 2014, Peer-reviwed
Scientific journal, English

Approximating the path-distance-width for AT-free graphs and graphs in related classes
Yota Otachi; Toshiki Saitoh; Katsuhisa Yamanaka; Shuji Kijima; Yoshio Okamoto; Hirotaka Ono; Yushi Uno; Koichi Yamazaki
DISCRETE APPLIED MATHEMATICS, 168, 69-77, May 2014, Peer-reviwed
Scientific journal, English

グラフ上のラベル付きトークン整列問題
山中 克久; エリック; ドメイン(MIT; 伊藤 健洋; 川原純; 清見 礼; 岡本 吉央; 斎藤 寿樹; 鈴木 顕; 内澤 啓; 宇野 毅明(N
電子情報通信学会コンピュテーション研究会資料, 2014, 2, 5-12, Apr. 2014
Symposium, Japanese

Computing the geodesic centers of a polygonal domain
Sang Won Bae; Matias Korman; Yoshio Okamoto
26th Canadian Conference on Computational Geometry, CCCG 2014, Canadian Conference on Computational Geometry, 20-25, 2014
International conference proceedings, English

Computing the L-1 Geodesic Diameter and Center of a Simple Polygon in Linear Time
Sang Won Bae; Matias Korman; Yoshio Okamoto; Haitao Wang
LATIN 2014: THEORETICAL INFORMATICS, 8392, 120-131, 2014, Peer-reviwed
International conference proceedings, English

Semantic Word Cloud Representations: Hardness and Approximation Algorithms
Lukas Barth; Sara Irina Fabrikant; Stephen G. Kobourov; Anna Lubiw; Martin Noellenburg; Yoshio Okamoto; Sergey Pupyrev; Claudio Squarcella; Torsten Ueckerdt; Alexander Wolff
LATIN 2014: THEORETICAL INFORMATICS, 8392, 514-525, 2014, Peer-reviwed
International conference proceedings, English

Free edge lengths in plane graphs
Zachary Abel; Robert Connelly; Sarah Eisenstat; Radoslav Fulek; Filip Morić; Yoshio Okamoto; Tibor Szabó; Csaba D. Tóth
Proceedings of the Annual Symposium on Computational Geometry, Association for Computing Machinery, 426-435, 2014, Peer-reviwed
International conference proceedings, English

Weight balancing on boundaries and Skeletons
Luis Barba; Otfried Cheong; Jean-Lou De Carufel; Michael Gene Dobbins; Rudolf Fleischer; Akitoshi Kawamura; Matias Korman; Yoshio Okamoto; János Pach; Yuan Tang; Takeshi Tokuyama; Sander Verdonschot; Tianhao Wang
Proceedings of the Annual Symposium on Computational Geometry, Association for Computing Machinery, 436-443, 2014, Peer-reviwed
International conference proceedings, English

Sankaku-Tori: An Old Western-Japanese Game Played on a Point Set
Takashi Horiyama; Masashi Kiyomi; Yoshio Okamoto; Ryuhei Uehara; Takeaki Uno; Yushi Uno; Yukiko Yamauchi
FUN WITH ALGORITHMS, 8496, 230-239, 2014, Peer-reviwed
International conference proceedings, English

Swapping Labeled Tokens on Graphs
Katsuhisa Yamanaka; Erik D. Demaine; Takehiro Ito; Jun Kawahara; Masashi Kiyomi; Yoshio Okamoto; Toshiki Saitoh; Akira Suzuki; Kei Uchizawa; Takeaki Uno
FUN WITH ALGORITHMS, 8496, 364-375, 2014, Peer-reviwed
International conference proceedings, English

Minimum-Cost b-Edge Dominating Sets on Trees
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
ALGORITHMS AND COMPUTATION, ISAAC 2014, 8889, 195-207, 2014, Peer-reviwed
International conference proceedings, English

The Geodesic Diameter of Polygonal Domains
Sang Won Bae; Matias Korman; Yoshio Okamoto
DISCRETE & COMPUTATIONAL GEOMETRY, 50, 2, 306-329, Sep. 2013, Peer-reviwed
Scientific journal, English

The complexity of the stamp folding problem
Takuya Umesato; Toshiki Saitoh; Ryuhei Uehara; Hiro Ito; Yoshio Okamoto
THEORETICAL COMPUTER SCIENCE, 497, 13-19, Jul. 2013, Peer-reviwed
Scientific journal, English

Exact and fixed-parameter algorithms for metro-line crossing minimization problems
Yoshio Okamoto; Yuichi Tatsu; Yushi Uno
Proceedings of 21st International Symposium on Graph Drawing (GD 2013), 520-521, 2013, Peer-reviwed
International conference proceedings, English

Querying two boundary points for shortest paths in a polygonal domain
Sang Won Bae; Yoshio Okamoto
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 45, 7, 284-293, Aug. 2012, Peer-reviwed
Scientific journal, English

Vertex angle and crossing angle resolution of leveled tree drawings
Walter Didimo; Michael Kaufmann; Giuseppe Liotta; Yoshio Okamoto; Andreas Spillner
INFORMATION PROCESSING LETTERS, 112, 16, 630-635, Aug. 2012, Peer-reviwed
Scientific journal, English

Reverse preferential spread in complex networks
Hiroshi Toyoizumi; Seiichi Tani; Naoto Miyoshi; Yoshio Okamoto
PHYSICAL REVIEW E, 86, 2, Aug. 2012, Peer-reviwed
Scientific journal, English

単位正方形上の一意被覆問題に対する近似アルゴリズム
伊藤 健洋; 中野 眞一; 岡本 吉央; 大舘 陽太; 上原 隆平; 宇野 毅明; 宇野 裕之
電子情報通信学会コンピュテーション研究会, 95-101, Jun. 2012
Symposium, English

Guest editors' foreword
Otfried Cheong; Yoshio Okamoto
International Journal of Computational Geometry and Applications, 22, 1, 1-2, Feb. 2012, Peer-reviwed
Scientific journal, English

Drawing (Complete) Binary Tanglegrams Hardness, Approximation, Fixed-Parameter Tractability
Kevin Buchin; Maike Buchin; Jaroslaw Byrka; Martin Noellenburg; Yoshio Okamoto; Rodrigo I. Silveira; Alexander Wolff
ALGORITHMICA, 62, 1-2, 309-332, Feb. 2012, Peer-reviwed
Scientific journal, English

Game Theory for Computer Scientists -Noncoop-erative Games (Advanced)-.
Makoto Yokoo; Atsushi Iwasaki; Yuko Sakurai; Yoshio Okamoto
Computer Software, 29, 3, 39-53, 2012, Peer-reviwed
Scientific journal, English

Efficient enumeration of the directed binary perfect phylogenies from incomplete data
Masashi Kiyomi; Yoshio Okamoto; Toshiki Saitoh
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7276, 248-259, 2012, Peer-reviwed
International conference proceedings, English

A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares
Takehiro Ito; Shin-Ichi Nakano; Yoshio Okamoto; Yota Otachi; Ryuhei Uehara; Takeaki Uno; Yushi Uno
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 7357, 24-35, 2012, Peer-reviwed
International conference proceedings, English

On Problems as Hard as CNF-SAT
Marek Cygan; Holger Dell; Daniel Lokshtanov; Daniel Marx; Jesper Nederlof; Yoshio Okamoto; Ramamohan Paturi; Saket Saurabh; Magnus Wahlstroem
2012 IEEE 27TH ANNUAL CONFERENCE ON COMPUTATIONAL COMPLEXITY (CCC), 74-84, 2012, Peer-reviwed
International conference proceedings, English

Minimum and maximum against k lies
Michael Hoffmann; Jiri Matousek; Yoshio Okamoto; Philipp; Zumstein
Chicago Journal of Theoretical Computer Science, 2012, 2, 1-10, 2012, Peer-reviwed
Scientific journal, English

On bipartite powers of bigraphs
Yoshio Okamoto; Yota Otachi; Ryuhei Uehara
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 14, 2, 11-20, 2012, Peer-reviwed
Scientific journal, English

A 4.31-Approximation for the Geometric Unique Coverage Problem on Unit Disks
Takehiro Ito; Shin-ichi Nakano; Yoshio Okamoto; Yota Otachi; Ryuhei Uehara; Takeaki Uno; Yushi Uno
ALGORITHMS AND COMPUTATION, ISAAC 2012, 7676, 372-381, 2012, Peer-reviwed
International conference proceedings, English

Universal Point Subsets for Planar Graphs
Patrizio Angelini; Carla Binucci; William Evans; Ferran Hurtado; Giuseppe Liotta; Tamara Mchedlidze; Henk Meijer; Yoshio Okamoto
ALGORITHMS AND COMPUTATION, ISAAC 2012, 7676, 423-432, 2012, Peer-reviwed
International conference proceedings, English

Area Bounds of Rectilinear Polygons Realized by Angle Sequences
Sang Won Bae; Yoshio Okamoto; Chan-Su Shin
ALGORITHMS AND COMPUTATION, ISAAC 2012, 7676, 629-638, 2012, Peer-reviwed
International conference proceedings, English

The t-pebbling number is eventually linear in t
Michael Hoffmann; Jiri Matousek; Yoshio Okamoto; Philipp Zumstein
ELECTRONIC JOURNAL OF COMBINATORICS, 18, 1, Jul. 2011, Peer-reviwed
Scientific journal, English

A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization
Yoshio Okamoto; Takeaki Uno
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 210, 1, 48-56, Apr. 2011, Peer-reviwed
Scientific journal, English

Adaptive Algorithms for Planar Convex Hull Problems
Hee-Kap Ahn; Yoshio Okamoto
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, E94D, 2, 182-189, Feb. 2011, Peer-reviwed
Scientific journal, English

Hardness results and an exact exponential algorithm for the spanning tree congestion problem
Yoshio Okamoto; Yota Otachi; Ryuhei Uehara; Takeaki Uno
Journal of Graph Algorithms and Applications, 15, 6, 727-751, 2011, Peer-reviwed
Scientific journal, English

Submodular fractional programming for balanced clustering
Yoshinobu Kawahara; Kiyohito Nagano; Yoshio Okamoto
PATTERN RECOGNITION LETTERS, 32, 2, 235-243, Jan. 2011, Peer-reviwed
Scientific journal, English

Approximability of the Path-Distance-Width for AT-free Graphs
Yota Otachi; Toshiki Saitoh; Katsuhisa Yamanaka; Shuji Kijima; Yoshio Okamoto; Hirotaka Ono; Yushi Uno; Koichi Yamazaki
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 6986, 271-+, 2011, Peer-reviwed
International conference proceedings, English

Dominating set counting in graph classes
Shuji Kijima; Yoshio Okamoto; Takeaki Uno
Proceedings of 17th Annual International Computing and Combinatorics Conference (COCOON 2011), Springer, 13-24, 2011, Peer-reviwed
International conference proceedings, English

Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
Yoshio Okamoto; Yota Otachi; Ryuhei Uehara; Takeaki Uno
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011, 6648, 452-462, 2011, Peer-reviwed
International conference proceedings, English

Improved Bounds for Wireless Localization
Tobias Christ; Michael Hoffmann; Yoshio Okamoto; Takeaki Uno
ALGORITHMICA, 57, 3, 499-516, Jul. 2010, Peer-reviwed
Scientific journal, English

On listing, sampling, and counting the chordal graphs with edge constraints
Shuji Kijima; Masashi Kiyomi; Yoshio Okamoto; Takeaki Uno
THEORETICAL COMPUTER SCIENCE, 411, 26-28, 2591-2601, Jun. 2010, Peer-reviwed
Scientific journal, English

支配集合数え上げ問題とグラフクラス
来嶋 秀治; 岡本 吉央; 宇野 毅明
電子情報通信学会コンピュテーション研究会, 9-15, Apr. 2010
Symposium, English

A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets
Ondrej Bilka; Kevin Buchin; Radoslav Fulek; Masashi Kiyomi; Yoshio Okamoto; Shin-ichi Tanigawa; Csaba D. Toth
The Electronic Journal of Combinatorics, 17, 2010, Peer-reviwed
Scientific journal, English

The Geodesic Diameter of Polygonal Domains
Sang Won Bae; Matias Korman; Yoshio Okamoto
ALGORITHMS-ESA 2010, 6346, 500-+, 2010, Peer-reviwed
International conference proceedings, English

Adaptive Algorithms for Planar Convex Hull Problems
Hee-Kap Ahn; Yoshio Okamoto
FRONTIERS IN ALGORITHMICS, 6213, 316-+, 2010, Peer-reviwed
International conference proceedings, English

Minimum and Maximum against k Lies
Michael Hoffmann; Jiri Matousek; Yoshio Okamoto; Philipp Zumstein
ALGORITHM THEORY - SWAT 2010, PROCEEDINGS, 6139, 139-+, 2010, Peer-reviwed
International conference proceedings, English

Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes
Yoshio Okamoto; Ryuhei Uehara; Takeaki Uno
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 5911, 296-+, 2010, Peer-reviwed
International conference proceedings, English

Untangling a Planar Graph
Xavier Goaoc; Jan Kratochvil; Yoshio Okamoto; Chan-Su Shin; Andreas Spillner; Alexander Wolff
DISCRETE & COMPUTATIONAL GEOMETRY, 42, 4, 542-569, Dec. 2009, Peer-reviwed
Scientific journal, English

The Holt-Klee condition for oriented matroids
Komei Fukuda; Sonoko Moriyama; Yoshio Okamoto
EUROPEAN JOURNAL OF COMBINATORICS, 30, 8, 1854-1867, Nov. 2009, Peer-reviwed
Scientific journal, English

Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes
Yoshio Okamoto; Ryuhei Uehara; Takeaki Uno
COMP2009-24, 109, 45-52, Jun. 2009
Symposium, English

FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES
Heidi Gebauer; Yoshio Okamoto
INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 20, 1, 25-44, Feb. 2009, Peer-reviwed
Scientific journal, English

How to make a picturesque maze.
Yoshio Okamoto; Ryuhei Uehara
Proceedings of the 21st Annual Canadian Conference on Computational Geometry, Vancouver, British Columbia, Canada, August 17-19, 2009, 137-140, 2009, Peer-reviwed

Querying Two Boundary Points for Shortest Paths in a Polygonal Domain (Extended Abstract)
Sang Won Bae; Yoshio Okamoto
ALGORITHMS AND COMPUTATION, PROCEEDINGS, 5878, 1054-+, 2009, Peer-reviwed
International conference proceedings, English

Drawing (Complete) Binary Tanglegrams Hardness, Approximation, Fixed-Parameter Tractability
Kevin Buchin; Maike Buchin; Jaroslaw Byrka; Martin Noellenburg; Yoshio Okamoto; Rodrigo I. Silveira; Alexander Wolff
GRAPH DRAWING, 5417, 324-+, 2009, Peer-reviwed
International conference proceedings, English

Local topology of the free complex of a two-dimensional generalized convex shelling
Yoshio Okamoto
DISCRETE MATHEMATICS, 308, 17, 3836-3846, Sep. 2008, Peer-reviwed
Scientific journal, English

Fair cost allocations under conflicts - a game-theoretic point of view
Yoshio Okamoto
DISCRETE OPTIMIZATION, 5, 1, 1-18, Feb. 2008, Peer-reviwed
Scientific journal, English

コーダルサンドイッチの列挙, ランダム生成, 数え上げについて
来嶋 秀治; 清見 礼; 岡本 吉央
数理解析研究所講究録 理論計算機科学の深化 : 新たな計算世界観を求めて, 1599, 148-153, 2008
Symposium, English

Counting the number of independent sets in chordal graphs
Yoshio Okamoto; Takeaki Uno; Ryuhei Uehara
Journal of Discrete Algorithms, Elsevier, 6, 2, 229-242, 2008, Peer-reviwed, We study some counting and enumeration problems for chordal graphs, especially concerning independent sets. We first provide the following efficient algorithms for a chordal graph: (1) a linear-time algorithm for counting the number of independent sets; (2) a linear-time algorithm for counting the number of maximum independent sets; (3) a polynomial-time algorithm for counting the number of independent sets of a fixed size. With similar ideas, we show that enumeration (namely, listing) of the independent sets, the maximum independent sets, and the independent sets of a fixed size in a chordal graph can be done in constant amortized time per output. On the other hand, we prove that the following problems for a chordal graph are #P-complete: (1) counting the number of maximal independent sets; (2) counting the number of minimum maximal independent sets. With similar ideas, we also show that finding a minimum weighted maximal independent set in a chordal graph is NP-hard, and even hard to approximate.
Scientific journal, English

Improved bounds for wireless localization
Tobias Christ; Michael Hoffmann; Yoshio Okamoto; Takeaki Uno
ALGORITHM THEORY - SWAT 2008, 5124, 77-+, 2008, Peer-reviwed
International conference proceedings, English

On listing, sampling, and counting the chordal graphs with edge constraints
Shuji Kijima; Masashi Kiyomi; Yoshio Okamoto; Takeaki Uno
COMPUTING AND COMBINATORICS, PROCEEDINGS, 5092, 458-+, 2008, Peer-reviwed
International conference proceedings, English

Moving vertices to make drawings plane
Xavier Goaoc; Jan Kratochvil; Yoshio Okamoto; Chan-Su Shin; Alexander Wolff
GRAPH DRAWING, 4875, 101-+, 2008, Peer-reviwed
International conference proceedings, English

Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs
Yota Otachi; Yoshio Okamoto; Koichi Yamazaki
DISCRETE APPLIED MATHEMATICS, 155, 17, 2383-2390, Oct. 2007, Peer-reviwed
Scientific journal, English

Matroid representation of clique complexes
Kenji Kashiwabara; Yoshio Okamoto; Takeaki Uno
DISCRETE APPLIED MATHEMATICS, 155, 15, 1910-1929, Sep. 2007, Peer-reviwed
Scientific journal, English

A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization
Yoshio Okamoto; Takeaki Uno
ALGORITHMS AND COMPUTATION, 4835, 609-+, 2007, Peer-reviwed
International conference proceedings, English

Fast exponential-time algorithms for the forest counting in graph classes
Heidi Gebauer; Yoshio Okamoto
Proceedings of 13th Computing: The Australasian Theory Symposium (CATS 2007), Australian Computer Society, 63-69, 2007, Peer-reviwed
International conference proceedings, English

The even outdegree conjecture for acyclic PLCP-cubes in dimension five
Sonoko Moriyama; Yoshio Okamoto
IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, E89D, 8, 2402-2404, Aug. 2006, Peer-reviwed
Scientific journal, English

The minimum weight triangulation problem with few inner points
M Hoffmann; Y Okamoto
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 34, 3, 149-158, Jul. 2006, Peer-reviwed
Scientific journal, English

Core stability of minimum coloring games
Thomas Bietenhader; Yoshio Okamoto
MATHEMATICS OF OPERATIONS RESEARCH, 31, 2, 418-431, May 2006, Peer-reviwed
Scientific journal, English

多目的最適化問題への列挙アルゴリズム理論からのアプローチ
岡本 吉央; 宇野 毅明
研究集会「最適化：モデリングとアルゴリズム」共同レポート, 15-25, Mar. 2006, Invited
Symposium, Japanese

The traveling salesman problem with few inner points
VG Deineko; M Hoffmann; Y Okamoto; GJ Woeginger
OPERATIONS RESEARCH LETTERS, 34, 1, 106-110, Jan. 2006, Peer-reviwed
Scientific journal, English

The affine representation theorem for abstract convex geometries
K Kashiwabara; M Nakamura; Y Okamoto
COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 30, 2, 129-144, Feb. 2005, Peer-reviwed
Scientific journal, English

Linear-time counting algorithms for independent sets in chordal graphs
Y Okamoto; T Uno; R Uehara
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 3787, 433-444, 2005, Peer-reviwed
Scientific journal, English

Counting the Independent Sets of a Chordal Graph
岡本 吉央; 宇野 毅明; 上原 隆平
第96回情報処理学会アルゴリズム研究会, 17-24, Jul. 2004
Symposium, English

Traveling salesman games with the Monge property
Y Okamoto
DISCRETE APPLIED MATHEMATICS, 138, 3, 349-369, Apr. 2004, Peer-reviwed
Scientific journal, English

Core stability of minimum coloring games
T Bietenhader; Y Okamoto
GRAPH -THEORETIC CONCEPTS IN COMPUTER SCIENCE, 3353, 389-401, 2004, Peer-reviwed
Scientific journal, English

The minimum weight triangulation problem with few inner points
M Hoffmann; Y Okamoto
PARAMETERIZED AND EXACT COMPUTATION, PROCEEDINGS, 3162, 200-212, 2004, Peer-reviwed
Scientific journal, English

The traveling salesman problem with few inner points
VG Deineko; M Hoffmann; Y Okamoto; GJ Woeginger
COMPUTING AND COMBINATORICS, PROCEEDINGS, 3106, 268-277, 2004, Peer-reviwed
Scientific journal, English

Submodularity of some classes of the combinatorial optimization games
Y Okamoto
MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 58, 1, 131-139, Oct. 2003, Peer-reviwed
Scientific journal, English

The forbidden minor characterization of line-search antimatroids of rooted digraphs
Y Okamoto; M Nakamura
DISCRETE APPLIED MATHEMATICS, 131, 2, 523-533, Sep. 2003, Peer-reviwed
Scientific journal, English

A greedy algorithm for convex geometries
K Kashiwabara; Y Okamoto
DISCRETE APPLIED MATHEMATICS, 131, 2, 449-465, Sep. 2003, Peer-reviwed
Scientific journal, English

Fair cost allocations under conflicts - A game-theoretic point of view
Y Okamoto
ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2906, 686-695, 2003, Peer-reviwed
Scientific journal, English

Greedy edge-disjoint paths in complete graphs
P Carmi; T Erlebach; Y Okamoto
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2880, 143-155, 2003, Peer-reviwed
Scientific journal, English

The free complex of a two-dimensional generalized convex shelling
Yoshio Okamoto
EUROCOMB'03 -- Abstracts, 289-293, 2003, Peer-reviwed
International conference proceedings, English

Matroid representation of clique complexes
K Kashiwabara; Y Okamoto; T Uno
COMPUTING AND COMBINATORICS, PROCEEDINGS, 2697, 192-201, 2003, Peer-reviwed
Scientific journal, English

Some properties of the core on convex geometries
Yoshio Okamoto
Mathematical Methods of Operations Research, 56, 377-386, 2002, Peer-reviwed
Scientific journal, English

ネットワーク型交渉ゲームの安定化アルゴリズム
伊藤健洋; 垣村尚徳; 神山直之; 小林佑輔; 岡本吉央
28 Feb. 2016, 情報処理学会研究報告(Web), 2016, AL-157, VOL.2016‐AL‐157,NO.3 (WEB ONLY), Japanese, 201602218370461602

1-C-3 木における最小費用b-辺支配集合問題(離散最適化(1))
伊藤 健洋; 垣村 尚徳; 神山 直之; 小林 佑輔; 岡本 吉央
公益社団法人日本オペレーションズ・リサーチ学会, 26 Mar. 2015, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2015, 44-45, Japanese, 110009981367

Minimum-Cost b-Edge Dominating Sets on Trees
Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
We consider the minimum-cost b-edge dominating set problem. This is a generalization of the edge dominating set problem, but the computational complexity for trees is an astonishing open problem. We make steps toward the resolution of this open problem in the following three directions. (1) We give the first combinatorial polynomial-time algorithm for paths. Prior to our work, the polynomial-time algorithm for paths used linear programming, and it was known that the linear-programming approach could not be extended to trees. Thus, our algorithm would yield an alternative approach to a possible polynomial-time algorithm for trees. (2) We give a fixed-parameter algorithm for trees with the number of leaves as a parameter. Thus, a possible NP-hardness proof for trees should make use of trees with unbounded number of leaves. (3) We give a fully polynomial-time approximation scheme for trees. Prior to our work, the best known approximation factor was two. If the problem is NP-hard, then a possible proof cannot be done via a gap-preserving reduction from any APX-hard problem unless P = NP., Information Processing Society of Japan (IPSJ), 24 Feb. 2015, IPSJ SIG Notes, 2015, 2, 1-6, English, 0919-6072, 110009877668, AN1009593X

Weight Balancing on Boundaries and Skeletons (New Streams of Computation Theory and Algorithms)
Barba Luis; Cheong Otfried; Carufel Jean-Lou De; Dobbins Michael; Fleischer Rudolf; Kawamura Akitoshi; Korman Matias; Okamoto Yoshio; Pach Janos; Tang Yuan; Tokuyama Takeshi; Verdonschot Sander; Wang Tianhao
Kyoto University, May 2014, RIMS Kokyuroku, 1894, 45-52, Japanese, 1880-2818, 110009804829, AN00061013

Guest editorial: Selected papers from ISAAC 2011
Takao Asano; Shin-Ichi Nakano; Yoshio Okamoto
Sep. 2013, Algorithmica, 67, 1, 1-2, English, 0178-4617, 84879268935

Computational complexity and an integer programming model of Shakashaka
DEMAINE Erik D.; OKAMOTO Yoshio; UEHARA Ryuhei; UNO Yushi
Shakashaka, one of the so-called "pencil-and-paper" puzzles like Sudoku, was proposed by Guten and has been popularized by the Japanese publisher Nikoli. The computational complexity of Shakashaka was not studied so far. We first prove that Shakashaka is NP-complete. Next we formulate Shakashaka as an integer programming problem. We apply the formulation to some instances appeared in a puzzle book, solve them by using an IP solver, and show the experimental results; each problem can be solved in a second., The Institute of Electronics, Information and Communication Engineers, 24 Apr. 2013, IEICE technical report. Theoretical foundations of Computing, 113, 14, 43-48, English, 0913-5685, 110009768472, AN10013152

GUEST EDITORS' FOREWORD
Takao Asano; Shin-Ichi Nakano; Yoshio Okamoto
Apr. 2013, INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 23, 2, 73-74, English, Others, 0218-1959, 1793-6357, WOS:000327447000001

グラフを通したパズル・ゲームの一般化
岡本 吉央
パズルやゲームの中には登場するモノの間の相互関係が重要になるものが多い.例えば,本特集における伊藤大雄氏の記事ではジャンケンにおける各手の関係を有向グラフとして見ることにより,その一般化を考察している.本稿ではほかの例として「アルクインの川渡りパズル」と「帽子パズル」を考察対象とする.この2つについては近年研究が進んでおり,そのなかで未解決である問題についても言及する., 公益社団法人日本オペレーションズ・リサーチ学会, 01 Mar. 2013, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, 58, 3, 161-166, Japanese, 0030-3674, 110009594408, AN00364999

On computing the nucleolus and the Shapley value of facility location games with two cost values
並河 雄紀; 岡本 吉央; 大舘 陽太
施設配置ゲームは施設配置問題から生じる協力ゲームである．この問題では，施設配置問題において各顧客が協力関係を築いて費用の最小化を行うと見なし，最小化した費用を顧客間でどのように分け合うかを協力ゲーム理論の解概念に基づいて考える．しかし，実際にそのような解を計算しようとすると，計算量理論の意味で難しいことが多い．本稿では，施設配置ゲームの一種である容量制約なし施設配置ゲームについて議論する．具体的には，施設の数が2個かつ費用が2種類に制限された場合に，凸ゲームと呼ばれる良い性質を持つクラスに属するための必要十分条件を示す．さらに，施設が2個かつ費用が2種類の場合にはシャープレイ値が顧客数の多項式時間計算可能であることを示す．We study facility location games, which arise from the facility location problem as a cooperative game. In this game, customers in the facility location problem minimize their cost through cooperation, and the minimized cost is distributed among the customers by a solution concept from cooperative game theory. However, computation of such a solution can be hard in the sense of computational complexity theory. We concentrate on an uncapacitated facility location game. When there are at most two facilities, and the cost is restricted to two values, we characterize a convex game, which has several nice properties. Furthermore, when there are at most two facilities, and the cost is restricted to two values, we show that the Shapley value can be computed in polynomial time in the size of customers., 22 Feb. 2013, 研究報告アルゴリズム（AL）, 2013, 3, 1-8, Japanese, 110009550136, AN1009593X

Game Theory for Computer Scientist : Mechanism Design (Advanced)
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
This tutorial focuses on designing a mechanism that achieves a socially desirable outcome or a goal of the designer that arises from some practical demands, as several advanced topics on <IT>mechanism design</IT> theory. We first briefly explains the theory of combinatorial auctions via the most well-known Vickrey-Clarke-Groves mechanism. Second, as an example that designs a new mechanism for a practical demand, we introduce false-name bids and illustrate how we improve a trivial robust mechanism against false-name bids. Furthermore, we explore models and several theoretical results on mechanisms of a keyword auction and a two-sided matching as other well-known topics of mechanism design theory., Japan Society for Software Science and Technology, 25 Jan. 2013, Computer Software, 30, 1, 34-52, Japanese, 0289-6540, 10031138249

Game Theory for Computer Scientists - Cooperative Games
Makoto Yokoo; Atsushi Iwasaki; Yuko Sakurai; Yoshio Okamoto
日本ソフトウェア科学会 ; 1984-, 2013, Computer Software, 30, 2, 33-51, English, 0289-6540, 10031151473, 84883333397

Game Theory for Computer Scientists — Cooperative Games —
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
This tutorial introduces a cooperative game theory which is one of main parts in game theory. A cooperative game theory consists of two major research topics. The first topic involves how to divide the value of the coalition among agents. We explain the desirable ways of dividing the rewards among cooperative agents, called solution concepts. The traditional cooperative game theory provides a number of solution concepts, such as the core, the Shapley value, and the nucleolus. We introduce some algorithms for dividing the obtained rewards among agents and show their computational complexities. The second topic involves partitioning a set of agents into coalitions so that the sum of the rewards of all coalitions is maximized. This is called Coalition Structure Generation problem (CSG). We explain efficient constraint optimization algorithms for solving the CSG problem. Furthermore, we introduce concise representation schemes for a characteristic function, since it is likely that we can solve solution concepts/CSG problem more efficiently by utilizing concise representation methods for a game., Japan Society for Software Science and Technology, 2013, Computer Software, 30, 2, 2_33-2_51, Japanese, 0289-6540, 130004892257

Game Theory for Computer Scientists : Mechanism Design (Basic)
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
This tutorial describes an overview of mechanism design theory, which investigates a rule or a protocol for multiple agents to make a social decision. The theory models the decision problem as a games of incomplete information, where each player cannot directly observe her opponents' types. Under the assumption that each agent behaves so as to maximize her individual utility, mechanism design theory analyzes how a player chooses her action under a mechanism, while designs a mechanism to achieve a socially desirable outcome or a goal of the designer. This tutorial first briefly explains games of incomplete information and the concept of mechanism design. Then, as a typical example, we focus on auctions that sell a single item and explain several theoretical results on mechanism design theory., Japan Society for Software Science and Technology, 25 Oct. 2012, Computer Software, 29, 4, 15-31, Japanese, 0289-6540, 10031077886

On Computing the Nucleolus and the Shapley Value of Facility Location Games
NAMIKAWA Takanori; OKAMOTO Yoshio; OTACHI Yota
We study facility location games, which arise from the facility location problem as a cooperative game. In this game, customers in the facility location problem minimize their cost through cooperation, and the minimized cost is distributed among the customers by a solution concept from cooperative game theory. However, computaion of such a solution can be hard in the sense of computational complexity theory. We concentrate on an uncapacitated facility location game. When there are at most two facilities, and the cost is restrited to two values, we characterize a convex game, which has several nice properties. Furthermore, for general uncapacitated facility location games, we exhibit a case in which the nucleolus and the Shapley value coincide., The Institute of Electronics, Information and Communication Engineers, 24 Oct. 2012, IEICE technical report. Theoretical foundations of Computing, 112, 272, 25-32, Japanese, 0913-5685, 110009636909, AN10013152

Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data
KIYOMI Masashi; OKAMOTO Yoshio; SAITOH Toshiki
We study a character-based phylogeny reconstruction problem when an incomplete set of data is given. More specifically, we consider the situation under the directed perfect phylogeny assumption with binary characters in which for some species the states of some characters are missing. Our main object is to give an efficient algorithm to enumerate (or list) all perfect phylogenies that can be obtained when the missing entries are completed. While a simple branch-and-bound algorithm (B&B) shows a theoretically good performance, we propose another approach based on a zero-suppressed binary decision diagram (ZDD). Experimental results on randomly generated data exhibit that the ZDD approach outperforms B&B. We also prove that counting the number of phylogenetic trees consistent with a given data is #P-complete, thus providing an evidence that an efficient random sampling seems hard. This article is a technical report without peer review, and its polished version will be published elsewhere., The Institute of Electronics, Information and Communication Engineers, 14 Jun. 2012, IEICE technical report. Theoretical foundations of Computing, 112, 93, 17-24, English, 0913-5685, 110009588447, AN10013152

Enumeration Fundamentals and Basic Algorithms
OKAMOTO Yoshio
列挙問題とは,与えられた条件を満たすものを漏れなく,重複なく出力する問題である.本稿では,列挙問題を解くためのアルゴリズム設計技法として基礎的なものを紹介する.まず,列挙アルゴリズムの効率の良さの測り方を導入する.その後で,部分集合列挙問題を例題として,分割法,グレイコード,逆探索法という三つの設計技法を紹介する.最後に,効率の良い列挙アルゴリズムを設計することが難しい列挙問題とその理由について言及する., The Institute of Electronics, Information and Communication Engineers, 01 Jun. 2012, The Journal of the Institute of Electronics, Information, and Communication Engineers, 95, 6, 477-483, Japanese, 0913-5693, 110009457693, AN1001339X

Introduction of Game Theory for Computer Scientists
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
Japan Society for Software Science and Technology, 25 Apr. 2012, Computer Software, 29, 2, 65-68, Japanese, 0289-6540, 10030311272

Game Theory for Computer Scientists : Noncooperative Games (Basic Theory)
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
Game theory is a mathematical study of interaction among rational players. This tutorial presents an overview of noncooperative game theory, specifically games in normal-form. In noncooperative game theory in normal-form, multiple players independently and simultaneously select their actions so as to maximize their own utilities. The obtained utility of a player is determined by combination of her own action and the actions of other players. In noncooperative games, various equilibrium concepts have been developed to predict the result of a game. First, we introduce basic notations and equilibrium concepts in noncoperative games. If we explicitly represent a normal form game, the size of the representation grows exponentially as the number of players increases. Thus, we explain the algorithms/computational costs to efficiently find Nash equilibria in graphical games and congestion games, which have been proposed as concise representation schema., Japan Society for Software Science and Technology, 25 Apr. 2012, Computer Software, 29, 2, 69-84, Japanese, 0289-6540, 10030311279

Special Issue: Selected Papers from the 21st Annual International Symposium on Algorithms and Computation FOREWORD
Otfried Cheong; Yoshio Okamoto
Feb. 2012, INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 22, 1, 1-2, English, Others, 0218-1959, WOS:000308707000001

Game Theory for Computer Scientists —Noncooperative Games (Advanced)—
YOKOO Makoto; IWASAKI Atsushi; SAKURAI Yuko; OKAMOTO Yoshio
This tutorial introduces Nash equilibrium which is the most important equilibrium concept in noncooperative games. In 2-player zero-sum normal form games, we can compute Nash equilibria in polynomial time in the number of pure strategies available to players. However, in complicated games in which players take turns choosing actions, the number of pure strategies becomes large. We explain algorithms that can compute Nash equilibria in complicated card games such as poker. On the other hand, it has not been shown whether Nash equlibria in 2-player general-sum games can be found in polynomial time. The concepts related to decision problems are not appropriate in order to discuss the computational complexity of finding Nash equilibria, since the existence of them has been already proven. Thus, we introduce the classes PPAD and PPAD-complete to characterize the complexity of computing Nash equilibria., Japan Society for Software Science and Technology, 2012, Computer Software, 29, 3, 3_39-3_53, Japanese, 0289-6540, 130004549284

Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
OKAMOTO YOSHIO; OTACHI YOTA; UEHARA RYUHEI; UNO TAKEAKI
The Institute of Electronics, Information and Communication Engineers, 30 Aug. 2011, IEICE technical report, 111, 195, 31-38, English, 0913-5685, 110008900047, AN10013152

Approximating the path-distance-width for k-cocomparability graphs
Yota Otachi; Toshiki Saitoh; Katsuhisa Yamanaka; Shuji Kijima; Yoshio Okamoto; Hirotaka Ono; Yushi Uno; Koichi Yamazaki
28 Feb. 2011, 研究報告アルゴリズム（AL）, 2011, 1, 1-8, English, 110008583076, AN1009593X

Preface
Takao Asano; Shin-Ichi Nakano; Yoshio Okamoto; Osamu Watanabe
2011, Lecture Notes in Computer Science, 7074, English, Others, 0302-9743, 84055193956

How to make a picturesque maze (Theoretical Computer Science and Its Applications)
Okamoto Yoshio; Uehara Ryuhei
Kyoto University, May 2009, RIMS Kokyuroku, 1649, 58-65, Japanese, 1880-2818, 110007105293, AN00061013

2-F-5 多目的最適化への列挙アルゴリズム理論からのアプローチ(数理計画(1))
岡本 吉央; 宇野 毅明
公益社団法人日本オペレーションズ・リサーチ学会, 14 Mar. 2006, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2006, 212-213, Japanese, 110006168732, AN00351206

第4回 離散最適化と協力ゲーム(2)
毛利 裕昭; 岡本 吉央
公益社団法人日本オペレーションズ・リサーチ学会, 01 Feb. 2003, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, 48, 2, 114-120, Japanese, 0030-3674, 110001183690, AN00364999

応用数理ハンドブック
岡本吉央
Dictionary or encycropedia, Japanese, Joint work, 離散システム (近似アルゴリズム), 朝倉書店, 25 Oct. 2013

Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra
Yoshio Okamoto
Japanese, Single translation, Springer Japan, 2010

離散数学のすすめ
Japanese, Joint work, 第3章「平面上の点集合から見た離散数学」, 現代数学社, 2010

Encyclopedia of Algorithms
English, Joint work, Traveling Sales Person with Few Inner Points, Springer, 2008

Lectures on Discrete Geometry
Yoshio Okamoto
Japanese, Single translation, Springer-Verlag Tokyo, 2005

Lectures on Polytopes
Masahiro Hachimori; Yoshio Okamoto
Japanese, Joint translation, Springer-Verlag Tokyo, 2003

Theory of Computation
The University of Electro-Communications

計算理論
電気通信大学

情報・通信工学基礎
The University of Electro-Communications

情報・通信工学基礎
The University of Electro-Communications

情報・通信工学基礎
電気通信大学

Mathematical Information Science Laboratory IIB
The University of Electro-Communications

Mathematical Information Science Laboratory IIA
The University of Electro-Communications

離散数学
The University of Electro-Communications

離散数理工学
The University of Electro-Communications

キャリア教育演習
The University of Electro-Communications

キャリア教育演習
電気通信大学

Introduction to Science and Technology Studies II
The University of Tokyo

科学技術社会論II
東京大学

Discrete Mathematical Engineering
The University of Electro-Communications

離散数理工学
電気通信大学

Graphs and Networks
The University of Electro-Communications

グラフとネットワーク
電気通信大学

最適化手法
中央大学

最適化手法
中央大学

数理科学特別講義VIII／数理科学特論8
九州大学

数理科学特別講義VIII／数理科学特論8
九州大学

情報数理科学特別講義D／情報数理科学特別講義H／情報数理科学特殊講義B
大阪府立大学

情報数理科学特別講義D／情報数理科学特別講義H／情報数理科学特殊講義B
大阪府立大学

Graduate Course of Science and Technology on Communications
The University of Electro-Communications

大学院総合コミュニケーション科学
電気通信大学

Information Engineering Laboratory
The University of Electro-Communications

情報工学工房
電気通信大学

Graduate Technical English
The University of Electro-Communications

大学院技術英語
電気通信大学

Mathematical Information Science Laboratory II A
The University of Electro-Communications

情報数理工学実験第二A
電気通信大学

Discrete Mathematics
The University of Electro-Communications

離散数学
電気通信大学

Foundation of Discrete Optimization
The University of Electro-Communications

離散最適化基礎論
電気通信大学

Mathematical Information Science Laboratory II B
The University of Electro-Communications

情報数理工学実験第二B
電気通信大学

Mathematical Analysis
The University of Electro-Communications

数理解析
電気通信大学

The Operations Research Society of Japan

Mathematical Optimization Society

European Association for Theoretical Computer Science

LA Symposium

The Institute of Electronics, Information and Communication Engineers

Product structures theorems and unified methods of algorithm design for geometrically constructed graphs
岡本 吉央
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), 23K10982
01 Apr. 2023 - 31 Mar. 2026

Fusion of Computer Science, Engineering and Mathematics Approaches for Expanding Combinatorial Reconfiguration
伊藤 健洋; 川原 純; 岡本 吉央; 鈴木 顕
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Tohoku University, Grant-in-Aid for Transformative Research Areas (B), 本研究は，研究領域「組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合」の総括班であり，その目的は「班間連携の促進」と「外部への広報活動」の大きく２つである．これらを実現するために，下記の通り活動を行った． まず，本年度の領域会議を2020年10月30日と2021年3月23日の２回完全オンラインにて開催した．１０月の領域会議では，本研究領域の全体像をメンバーらと再確認した．３月の領域会議では，班間連携を促進するためにも，各計画研究班の半年間の研究動向を報告し合い，研究討論を行った．また，１０月，３月の領域会議ともに，同日に一般公開のシンポジウムも併催した．１０月の公開シンポジウムは，キックオフミーティングと銘打って，本研究領域の目的と計画を中心に解説した．３月の公開シンポジウムでは，招待講演も企画した． さらにオンラインでは，組合せ遷移のセミナー・勉強会を継続して行った．2020年度中には７回開催し，それらは全て一般公開している．セミナー・勉強会は，本研究領域のメンバーが自身の研究を紹介することで，その背景分野を互いに勉強し合い，班間連携の促進につなげることを目的としている． この他にもアウトリーチ活動として，本研究領域Webサイトの開設，ニュースレター創刊号の発行，電気通信大学主催の産学官連携イベントでの発表などを行った． また，大容量メモリ搭載計算サーバを設置し，本研究領域のメンバーが利用できるように環境整備を行った．, 20H05792
Oct. 2020 - Mar. 2023

数学アプローチによる組合せ遷移の展開：活用事例を手がかりとして新解法へ
Principal investigator
Oct. 2020 - Mar. 2023

大規模配位空間の最適化理論：離散構造論の視点を中心にして
Scientific research (C), general, Principal investigator
Apr. 2020 - Mar. 2023

パラメータ化計算量による幾何近似アルゴリズム
JSPS, 二国間事業共同研究 (インド (DST) との共同研究)
2019 - 2021

内在構造に基づく大規模グラフの高速処理とその理論基盤構築
栢森情報科学振興財団, 研究助成
Jan. 2017 - Dec. 2018

計算幾何学と計算トポロジーが拓く新時代データ解析の理論基盤
Scientific research (C), general, Principal investigator
2015 - 2017

持続可能な発展のための資源配分メカニズム設計理論の構築
Scientific research (S), Coinvestigator
2012 - 2016

最適化技法との融合による計算限界解析法の深化
Scientific research on innovative areas, research under a proposed research project, Coinvestigator, 新学術領域研究（研究領域提案型）
2012 - 2016

厳密計算における信頼性とその理論保証のための数理的アプローチ
Young scientists (B), Principal investigator
2012 - 2014

大規模なセンサネットワーク位置推定問題の数値解法に関する研究
KOJIMA Masakazu; OKAMOTO Yoshio; MIYOSHI Naoto; YAMASHITA Makoto; FUJISAWA Katsuki
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Tokyo Institute of Technology, Scientific research (B), general, Coinvestigator, Sensor network localization (SNL) problems have attracted considerable research interests for a broad spectrum of applications such as environmental monitoring, traffic control and structural assessment. The problem is to estimate the locations of n sensors of unknown positions using given distances and some m sensors of known positions (called anchors) in a sensor network of m+n sensors. Finding the solutions of this problem is known to be NP-hard. Thus, approximating the solution of this problem has been dealt with from many angles. In this project, we have studied numerical methods based on the semidefinite programming (SDP) relaxation．The SDP relaxation can provide approximate solutions with accuracy, but the computational cost of solving SNL problems by the SDP relaxation becomes expensive rapidly as their sizes increase. To avoid this difficulty, we fully exploited the sparsity which were involved in large scale SNL problems and improved the performance of the SDP solver SDPA. As a final product, we released a software package SFSDP that can solve large-scale sensor network localization problems in high speed., 22310089
2010 - 2012

多面体的組合せ論に基づく数え上げアルゴリズム設計理論の構築
OKAMOTO Yoshio
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Young scientists (B), Principal investigator, Results on counting problems for graphs, counting problems for discrete and computational geometry, and their applications to optimization problems were obtained. For example, the computational complexity of counting the dominating sets in a graph was investigated from the perspective of graph classes, and a polynomial-time algorithm to find a global optimal solution to the distance function maximization was developed by efficiently enumerating all local optimal solutions. These results were presented in refereed international journals and refereed international conferences., 21700009
2009 - 2011

グラフ・ネットワーク上のゲーム理論に対するアルゴリズム理論的厳密アプローチ
OKAMOTO Yoshio
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, Young scientists (B), Principal investigator, グラフ・ネットワークに関わる協力ゲーム理論について,アルゴリズム理論・計算理論の観点から精緻な議論を行った.特に,最小彩色ゲームと呼ばれる費用分担問題に対して,今までに提案された公平な費用分担の中のいくつかが効率よく計算できることを示した.それに加えて,コア安定性問題に対する計算量理論的な解析も行った.さらに,最小費用全域木ゲームと呼ばれる費用分担問題に対して,公平費用分担が効率よく計算できるための十分条件である劣モジュラ性を満たす場合の考察をした., 18710130
2006 - 2008

実践的な列挙アルゴリズムの理論構築
宇野 毅明; 中野 眞一; 松井 泰子; 岡本 吉央; 清見 礼
日本学術振興会, 科学研究費助成事業, 国立情報学研究所, Scientific research on priority areas (planned), Coinvestigator, 研究分担者となったのは2004年度から．, 16092227
2004 - 2007

匠ガールプロジェクト2024「夏休みは電通大でラボ体験」
Appearance, 電気通信大学, 見える暗号を作ってみよう
13 Jul. 2024

31st International Computing and Combinatorics Conference (COCOON 2025)
Peer review, Mar. 2025 - May 2025

19th International Conference and Workshops on Algorithms and Computation (WALCOM 2025)
Peer review, Sep. 2024 - Nov. 2024