岡本　吉央

情報・ネットワーク工学専攻教授
Ⅰ類（情報系）教授
研究者情報

学位

  • 教養学士, 東京大学, 1999年03月
  • 修士（学術）, 東京大学, 2001年03月
  • Ph.D., スイス連邦工科大学チューリッヒ校, 2005年03月

研究キーワード

  • 離散アルゴリズム
  • 離散最適化
  • 離散数学
  • 計算幾何学・離散幾何学
  • グラフアルゴリズム
  • 組合せ遷移
  • アルゴリズム的ゲーム理論

研究分野

  • 情報通信, 情報学基礎論
  • 情報通信, 数理情報学
  • 自然科学一般, 数学基礎
  • 自然科学一般, 応用数学、統計数学
  • 社会基盤（土木・建築・防災）, 社会システム工学
  • 社会基盤（土木・建築・防災）, 安全工学

経歴

  • 2017年04月01日
    電気通信大学, 大学院情報理工学研究科 情報・ネットワーク工学専攻, 教授
  • 2016年04月01日 - 2017年03月31日
    電気通信大学, 大学院情報理工学研究科 情報・ネットワーク工学専攻, 准教授
  • 2012年04月01日 - 2016年03月31日
    電気通信大学, 大学院情報理工学研究科 情報・通信工学専攻, 准教授
  • 2010年10月01日 - 2012年03月31日
    北陸先端科学技術大学院大学, 大学院教育イニシアティブセンター, 特任准教授
  • 2007年12月01日 - 2010年09月30日
    東京工業大学, 大学院情報理工学研究科, 特任准教授
  • 2007年04月01日 - 2007年11月30日
    豊橋技術科学大学, 工学部 情報工学系, 助教
  • 2005年04月01日 - 2007年03月31日
    豊橋技術科学大学, 工学部 情報工学系, 助手

学歴

  • 2002年04月 - 2005年03月
    スイス連邦工科大学チューリッヒ校, 情報科学部, スイス連邦
  • 1999年04月 - 2001年03月
    東京大学, 総合文化研究科, 広域科学専攻 広域システム科学系
  • 1995年04月 - 1999年03月
    東京大学, 教養学部, 基礎科学科第二
  • 1992年04月 - 1995年03月
    岡崎高等学校, 普通科
研究活動情報

受賞

  • 受賞日 2025年06月
    Outstanding Reviewer Award of SoCG 2025, Yoshio Okamoto
    国際学会・会議・シンポジウム等の賞
  • 受賞日 2024年01月
    情報処理学会
    2023年度コンピュータサイエンス領域功績賞, 岡本吉央
    国内学会・会議・シンポジウム等の賞
  • 受賞日 2022年03月
    日本オペレーションズ・リサーチ学会
    日本オペレーションズ・リサーチ学会フェロー
  • 受賞日 2021年09月
    船井ベストペーパー賞, 岡本吉央;伊藤健洋;垣村尚徳;神山直之;小林佑輔
    国内学会・会議・シンポジウム等の賞
  • 受賞日 2020年09月
    日本オペレーションズ・リサーチ学会
    日本オペレーションズ・リサーチ学会第10回研究賞
    国内学会・会議・シンポジウム等の賞
  • 受賞日 2015年
    日本ソフトウェア科学会
    日本ソフトウェア科学会第5回解説論文賞, 横尾真;岩崎敦;櫻井祐子;岡本吉央
    国内学会・会議・シンポジウム等の賞
  • 受賞日 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, 出版日 2025年05月, 査読付
    研究論文（学術雑誌）
    DOI URL
  • 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, 出版日 2025年04月, 査読付
    研究論文（学術雑誌）
    DOI URL
  • 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, 出版日 2025年04月, 査読付, 国際誌
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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, 出版日 2025年03月, 査読付
    研究論文（学術雑誌）
    URL
    DOI URL
  • 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, 出版日 2024年12月, 査読付, 国際誌, 国際共著論文
    研究論文（学術雑誌）
    DOI URL
  • 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, 出版日 2024年06月01日, 査読付, 国際誌
    研究論文（国際会議プロシーディングス）
    URL
    DOI URL
  • 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, 出版日 2023年12月, 査読付
    研究論文（国際会議プロシーディングス）
    DOI URL
  • 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, 出版日 2023年11月, 査読付
    研究論文（学術雑誌）
    DOI URL
  • Algorithmic Theory of Qubit Routing
    Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
    WADS, 掲載ページ 533-546, 出版日 2023年07月, 査読付
    研究論文（国際会議プロシーディングス）
    URL
    URL 2
    DOI URL
  • 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, 出版日 2023年07月, 査読付
    研究論文（国際会議プロシーディングス）
    URL
    URL 2
    DOI URL
  • 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, 出版日 2023年07月, 査読付
    研究論文（国際会議プロシーディングス）
    URL
    URL 2
    DOI URL
  • 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, 出版日 2023年06月, 査読付
    研究論文（国際会議プロシーディングス）
    URL
    URL 2
    DOI URL
  • Algorithmic Theory of Qubit Routing
    Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
    CoRR, abs/2305.02059巻, 出版日 2023年05月
    研究論文（学術雑誌）
    URL
    DOI URL
  • 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巻, 出版日 2023年04月
    研究論文（学術雑誌）
    URL
    DOI URL
  • 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, 出版日 2023年01月31日, 査読付
    研究論文（学術雑誌）
    URL
    DOI URL
  • 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, 出版日 2023年01月, 査読付
    研究論文（学術雑誌）
    DOI URL
  • 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, 出版日 2022年11月, 査読付
    論文集(書籍)内論文
    URL
    DOI URL
  • 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巻, 出版日 2022年10月
    研究論文（学術雑誌）
    URL
    DOI URL
  • Core Challenge 2022: Solver and Graph Descriptions
    Takehide Soh; Yoshio Okamoto; Takehiro Ito
    CoRR, abs/2208.02495巻, 出版日 2022年08月
    研究論文（学術雑誌）
    URL
    DOI URL
  • 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, 出版日 2022年06月, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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, 出版日 2022年06月, 査読付, 国際共著論文
    英語
    DOI URL
  • Reforming an Envy-Free Matching
    Takehiro Ito; Yuni Iwamasa; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yuta Nozaki; Yoshio Okamoto; Kenta Ozeki
    AAAI, 掲載ページ 5084-5091, 出版日 2022年06月, 査読付
    研究論文（国際会議プロシーディングス）
    URL
    URL 2
  • 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, 出版日 2022年06月, 査読付
    研究論文（学術雑誌）
    DOI URL
  • 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, 出版日 2022年05月, 査読付
    研究論文（学術雑誌）
    DOI URL
  • Linear-Time Recognition of Double-Threshold Graphs.
    Yusuke Kobayashi 0001; Yoshio Okamoto; Yota Otachi; Yushi Uno
    Algorithmica, 84巻, 4号, 掲載ページ 1163-1181, 出版日 2022年
    研究論文（学術雑誌）
    URL
    DOI URL
  • 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, 出版日 2022年01月, 査読付
    研究論文（国際会議プロシーディングス）
    URL
    URL 2
    DOI URL
  • 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巻, 出版日 2021年10月
    研究論文（学術雑誌）
    URL
    URL 2
  • 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, 出版日 2021年02月, 査読付
    研究論文（学術雑誌）
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • Algorithms for gerrymandering over graphs.
    Takehiro Ito; Naoyuki Kamiyama; Yusuke Kobayashi 0001; Yoshio Okamoto
    Theor. Comput. Sci., 868巻, 掲載ページ 30-45, 出版日 2021年, 査読付
    研究論文（学術雑誌）
    URL
    DOI URL
  • 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年, 査読付
    研究論文（学術雑誌）, 英語
  • Algorithmic enumeration of surrounding polygons
    Katsuhisa Yamanaka; David Avis; Takashi Horiyama; Yoshio Okamoto; Ryuhei Uehara; Tanami Yamauchi
    Discrete Applied Mathematics, Elsevier BV, 出版日 2020年04月, 査読付
    研究論文（学術雑誌）
    DOI URL
  • 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巻, 出版日 2020年01月01日
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    URL
    URL 2
    DOI URL
  • Subgraph Isomorphism on Graph Classes that Exclude a Substructure
    Hans L. Bodlaender; Tesshu Hanaka; Yoshio Okamoto; Yota Otachi; Tom C. van; der Zanden
    Proceedings of 11th International Conference on Algorithms and Complexity (CIAC 2019), Springer, 82巻, 12号, 掲載ページ 87-98, 出版日 2019年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    URL
    URL 2
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）
    DOI URL
  • Computing the Geodesic Centers of a Polygonal Domain
    Sang Won Bae; Matias Korman; Yoshio Okamoto
    Computational Geometry: Theory and Applications, 77巻, 掲載ページ 3-9, 出版日 2019年, 査読付
    研究論文（学術雑誌）, 英語
  • 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年, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（学術雑誌）, 英語
    URL
    DOI URL
  • 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年, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（学術雑誌）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    URL
  • 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年, 査読付
    研究論文（学術雑誌）, 英語
  • 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年, 査読付
    論文集(書籍)内論文, 英語
    URL
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    URL
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    URL
    URL 2
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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, 出版日 2017年06月01日, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    DOI URL
  • Efficient stabilization of cooperative matching games
    Takehiro Ito; Naonori Kakimura; Naoyuki Kamiyama; Yusuke Kobayashi; Yoshio Okamoto
    THEORETICAL COMPUTER SCIENCE, 677巻, 掲載ページ 69-82, 出版日 2017年05月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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, 出版日 2017年04月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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, 出版日 2017年04月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（学術雑誌）, 英語
    URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    DOI URL
  • Extended formulations for sparsity matroids
    Satoru Iwata; Naoyuki Kamiyama; Naoki Katoh; Shuji Kijima; Yoshio Okamoto
    MATHEMATICAL PROGRAMMING, 158巻, 1-2号, 掲載ページ 565-574, 出版日 2016年07月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Computational Complexity of Sequential Token Swapping Problem (コンピュテーション)
    山中 克久; ドメイン エリック; 堀山 貴史; 河村 彰星; 中野 眞一; 岡本 吉央; 斎藤 寿樹; 鈴木 顕; 上原 隆平; 宇野 毅明
    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 電子情報通信学会, 116巻, 116号, 掲載ページ 115-121, 出版日 2016年06月24日
    英語
  • シーケンシャルな交換による色付きトークン整列問題の計算複雑さ
    山中 克久; エリック ドメイン; 堀山 貴史; 河村 彰星; 中野 眞一; 岡本 吉央; 斎藤 寿樹; 鈴木 顕; 上原 隆平; 宇野 毅明
    第158回アルゴリズム研究会, 掲載ページ 1-7, 出版日 2016年06月
    研究論文（研究会，シンポジウム資料等）, 日本語
  • 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号, 出版日 2016年06月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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, 出版日 2016年01月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • On the treewidth of toroidal grids
    Masashi Kiyomi; Yoshio Okamoto; Yota Otachi
    DISCRETE APPLIED MATHEMATICS, 198巻, 掲載ページ 303-306, 出版日 2016年01月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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, 出版日 2015年08月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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, 出版日 2015年07月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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, 出版日 2015年06月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Polynomial-time approximability of the k-Sink Location problem.
    Rémy Belmonte; Yuya Higashikawa; Naoki Katoh; Yoshio Okamoto
    CoRR, abs/1503.02835巻, 出版日 2015年
    URL
  • 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, 出版日 2014年08月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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, 出版日 2014年06月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Submodularity of minimum-cost spanning tree games
    Masayuki Kobayashi; Yoshio Okamoto
    NETWORKS, 63巻, 3号, 掲載ページ 231-238, 出版日 2014年05月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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, 出版日 2014年05月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • グラフ上のラベル付きトークン整列問題
    山中 克久; エリック; ドメイン(MIT; 伊藤 健洋; 川原純; 清見 礼; 岡本 吉央; 斎藤 寿樹; 鈴木 顕; 内澤 啓; 宇野 毅明(N
    電子情報通信学会コンピュテーション研究会資料, 2014巻, 2号, 掲載ページ 5-12, 出版日 2014年04月
    研究論文（研究会，シンポジウム資料等）, 日本語
  • 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年
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    DOI URL
  • The Geodesic Diameter of Polygonal Domains
    Sang Won Bae; Matias Korman; Yoshio Okamoto
    DISCRETE & COMPUTATIONAL GEOMETRY, 50巻, 2号, 掲載ページ 306-329, 出版日 2013年09月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • The complexity of the stamp folding problem
    Takuya Umesato; Toshiki Saitoh; Ryuhei Uehara; Hiro Ito; Yoshio Okamoto
    THEORETICAL COMPUTER SCIENCE, 497巻, 掲載ページ 13-19, 出版日 2013年07月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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, 出版日 2012年08月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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, 出版日 2012年08月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Reverse preferential spread in complex networks
    Hiroshi Toyoizumi; Seiichi Tani; Naoto Miyoshi; Yoshio Okamoto
    PHYSICAL REVIEW E, 86巻, 2号, 出版日 2012年08月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 単位正方形上の一意被覆問題に対する近似アルゴリズム
    伊藤 健洋; 中野 眞一; 岡本 吉央; 大舘 陽太; 上原 隆平; 宇野 毅明; 宇野 裕之
    電子情報通信学会コンピュテーション研究会, 掲載ページ 95-101, 出版日 2012年06月
    研究論文（研究会，シンポジウム資料等）, 英語
  • Guest editors' foreword
    Otfried Cheong; Yoshio Okamoto
    International Journal of Computational Geometry and Applications, 22巻, 1号, 掲載ページ 1-2, 出版日 2012年02月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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, 出版日 2012年02月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Game Theory for Computer Scientists -Noncoop-erative Games (Advanced)-.
    Makoto Yokoo; Atsushi Iwasaki; Yuko Sakurai; Yoshio Okamoto
    Computer Software, 29巻, 3号, 掲載ページ 39-53, 出版日 2012年, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（学術雑誌）, 英語
  • On bipartite powers of bigraphs
    Yoshio Okamoto; Yota Otachi; Ryuhei Uehara
    DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 14巻, 2号, 掲載ページ 11-20, 出版日 2012年, 査読付
    研究論文（学術雑誌）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • The t-pebbling number is eventually linear in t
    Michael Hoffmann; Jiri Matousek; Yoshio Okamoto; Philipp Zumstein
    ELECTRONIC JOURNAL OF COMBINATORICS, 18巻, 1号, 出版日 2011年07月, 査読付
    研究論文（学術雑誌）, 英語
  • 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, 出版日 2011年04月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Adaptive Algorithms for Planar Convex Hull Problems
    Hee-Kap Ahn; Yoshio Okamoto
    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS, E94D巻, 2号, 掲載ページ 182-189, 出版日 2011年02月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Submodular fractional programming for balanced clustering
    Yoshinobu Kawahara; Kiyohito Nagano; Yoshio Okamoto
    PATTERN RECOGNITION LETTERS, 32巻, 2号, 掲載ページ 235-243, 出版日 2011年01月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
    URL
    URL 2
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • Improved Bounds for Wireless Localization
    Tobias Christ; Michael Hoffmann; Yoshio Okamoto; Takeaki Uno
    ALGORITHMICA, 57巻, 3号, 掲載ページ 499-516, 出版日 2010年07月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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, 出版日 2010年06月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 支配集合数え上げ問題とグラフクラス
    来嶋 秀治; 岡本 吉央; 宇野 毅明
    電子情報通信学会コンピュテーション研究会, 掲載ページ 9-15, 出版日 2010年04月
    研究論文（研究会，シンポジウム資料等）, 英語
  • 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年, 査読付
    研究論文（学術雑誌）, 英語
  • The Geodesic Diameter of Polygonal Domains
    Sang Won Bae; Matias Korman; Yoshio Okamoto
    ALGORITHMS-ESA 2010, 6346巻, 掲載ページ 500-+, 出版日 2010年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • Adaptive Algorithms for Planar Convex Hull Problems
    Hee-Kap Ahn; Yoshio Okamoto
    FRONTIERS IN ALGORITHMICS, 6213巻, 掲載ページ 316-+, 出版日 2010年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • Minimum and Maximum against k Lies
    Michael Hoffmann; Jiri Matousek; Yoshio Okamoto; Philipp Zumstein
    ALGORITHM THEORY - SWAT 2010, PROCEEDINGS, 6139巻, 掲載ページ 139-+, 出版日 2010年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • Untangling a Planar Graph
    Xavier Goaoc; Jan Kratochvil; Yoshio Okamoto; Chan-Su Shin; Andreas Spillner; Alexander Wolff
    DISCRETE & COMPUTATIONAL GEOMETRY, 42巻, 4号, 掲載ページ 542-569, 出版日 2009年12月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • The Holt-Klee condition for oriented matroids
    Komei Fukuda; Sonoko Moriyama; Yoshio Okamoto
    EUROPEAN JOURNAL OF COMBINATORICS, 30巻, 8号, 掲載ページ 1854-1867, 出版日 2009年11月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ
    Yoshio Okamoto; Ryuhei Uehara; Takeaki Uno
    電子情報通信学会コンピュテーション研究会, 109号, 掲載ページ 45-52, 出版日 2009年06月
    研究論文（研究会，シンポジウム資料等）, 英語
  • 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, 出版日 2009年02月, 査読付
    研究論文（学術雑誌）, 英語
  • 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年, 査読付
    URL
    URL 2
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • Local topology of the free complex of a two-dimensional generalized convex shelling
    Yoshio Okamoto
    DISCRETE MATHEMATICS, 308巻, 17号, 掲載ページ 3836-3846, 出版日 2008年09月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Fair cost allocations under conflicts - a game-theoretic point of view
    Yoshio Okamoto
    DISCRETE OPTIMIZATION, 5巻, 1号, 掲載ページ 1-18, 出版日 2008年02月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • コーダルサンドイッチの列挙, ランダム生成, 数え上げについて
    来嶋 秀治; 清見 礼; 岡本 吉央
    数理解析研究所講究録 理論計算機科学の深化 : 新たな計算世界観を求めて, 1599巻, 掲載ページ 148-153, 出版日 2008年
    研究論文（研究会，シンポジウム資料等）, 英語
  • 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年, 査読付, 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.
    研究論文（学術雑誌）, 英語
    URL
    DOI URL
  • Improved bounds for wireless localization
    Tobias Christ; Michael Hoffmann; Yoshio Okamoto; Takeaki Uno
    ALGORITHM THEORY - SWAT 2008, 5124巻, 掲載ページ 77-+, 出版日 2008年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • Moving vertices to make drawings plane
    Xavier Goaoc; Jan Kratochvil; Yoshio Okamoto; Chan-Su Shin; Alexander Wolff
    GRAPH DRAWING, 4875巻, 掲載ページ 101-+, 出版日 2008年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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, 出版日 2007年10月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Matroid representation of clique complexes
    Kenji Kashiwabara; Yoshio Okamoto; Takeaki Uno
    DISCRETE APPLIED MATHEMATICS, 155巻, 15号, 掲載ページ 1910-1929, 出版日 2007年09月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • 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, 出版日 2006年08月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • The minimum weight triangulation problem with few inner points
    M Hoffmann; Y Okamoto
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 34巻, 3号, 掲載ページ 149-158, 出版日 2006年07月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Core stability of minimum coloring games
    Thomas Bietenhader; Yoshio Okamoto
    MATHEMATICS OF OPERATIONS RESEARCH, 31巻, 2号, 掲載ページ 418-431, 出版日 2006年05月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 多目的最適化問題への列挙アルゴリズム理論からのアプローチ
    岡本 吉央; 宇野 毅明
    研究集会「最適化：モデリングとアルゴリズム」共同レポート, 掲載ページ 15-25, 出版日 2006年03月, 招待
    研究論文（研究会，シンポジウム資料等）, 日本語
  • The traveling salesman problem with few inner points
    VG Deineko; M Hoffmann; Y Okamoto; GJ Woeginger
    OPERATIONS RESEARCH LETTERS, 34巻, 1号, 掲載ページ 106-110, 出版日 2006年01月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • The affine representation theorem for abstract convex geometries
    K Kashiwabara; M Nakamura; Y Okamoto
    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 30巻, 2号, 掲載ページ 129-144, 出版日 2005年02月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • 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年, 査読付
    研究論文（学術雑誌）, 英語
  • Counting the Independent Sets of a Chordal Graph
    岡本 吉央; 宇野 毅明; 上原 隆平
    第96回情報処理学会アルゴリズム研究会, 掲載ページ 17-24, 出版日 2004年07月
    研究論文（研究会，シンポジウム資料等）, 英語
  • Traveling salesman games with the Monge property
    Y Okamoto
    DISCRETE APPLIED MATHEMATICS, 138巻, 3号, 掲載ページ 349-369, 出版日 2004年04月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • Core stability of minimum coloring games
    T Bietenhader; Y Okamoto
    GRAPH -THEORETIC CONCEPTS IN COMPUTER SCIENCE, 3353巻, 掲載ページ 389-401, 出版日 2004年, 査読付
    研究論文（学術雑誌）, 英語
  • The minimum weight triangulation problem with few inner points
    M Hoffmann; Y Okamoto
    PARAMETERIZED AND EXACT COMPUTATION, PROCEEDINGS, 3162巻, 掲載ページ 200-212, 出版日 2004年, 査読付
    研究論文（学術雑誌）, 英語
  • The traveling salesman problem with few inner points
    VG Deineko; M Hoffmann; Y Okamoto; GJ Woeginger
    COMPUTING AND COMBINATORICS, PROCEEDINGS, 3106巻, 掲載ページ 268-277, 出版日 2004年, 査読付
    研究論文（学術雑誌）, 英語
  • Submodularity of some classes of the combinatorial optimization games
    Y Okamoto
    MATHEMATICAL METHODS OF OPERATIONS RESEARCH, 58巻, 1号, 掲載ページ 131-139, 出版日 2003年10月, 査読付
    研究論文（学術雑誌）, 英語
    DOI URL
  • The forbidden minor characterization of line-search antimatroids of rooted digraphs
    Y Okamoto; M Nakamura
    DISCRETE APPLIED MATHEMATICS, 131巻, 2号, 掲載ページ 523-533, 出版日 2003年09月, 査読付
    研究論文（学術雑誌）, 英語
  • A greedy algorithm for convex geometries
    K Kashiwabara; Y Okamoto
    DISCRETE APPLIED MATHEMATICS, 131巻, 2号, 掲載ページ 449-465, 出版日 2003年09月, 査読付
    研究論文（学術雑誌）, 英語
  • Fair cost allocations under conflicts - A game-theoretic point of view
    Y Okamoto
    ALGORITHMS AND COMPUTATION, PROCEEDINGS, 2906巻, 掲載ページ 686-695, 出版日 2003年, 査読付
    研究論文（学術雑誌）, 英語
  • Greedy edge-disjoint paths in complete graphs
    P Carmi; T Erlebach; Y Okamoto
    GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, 2880巻, 掲載ページ 143-155, 出版日 2003年, 査読付
    研究論文（学術雑誌）, 英語
  • The free complex of a two-dimensional generalized convex shelling
    Yoshio Okamoto
    EUROCOMB'03 -- Abstracts, 掲載ページ 289-293, 出版日 2003年, 査読付
    研究論文（国際会議プロシーディングス）, 英語
  • Matroid representation of clique complexes
    K Kashiwabara; Y Okamoto; T Uno
    COMPUTING AND COMBINATORICS, PROCEEDINGS, 2697巻, 掲載ページ 192-201, 出版日 2003年, 査読付
    研究論文（学術雑誌）, 英語
  • Some properties of the core on convex geometries
    Yoshio Okamoto
    Mathematical Methods of Operations Research, 56巻, 掲載ページ 377-386, 出版日 2002年, 査読付
    研究論文（学術雑誌）, 英語

MISC

  • ネットワーク型交渉ゲームの安定化アルゴリズム
    伊藤健洋; 垣村尚徳; 神山直之; 小林佑輔; 岡本吉央
    出版日 2016年02月28日, 情報処理学会研究報告(Web), 2016巻, AL-157号, 掲載ページ VOL.2016‐AL‐157,NO.3 (WEB ONLY), 日本語, 201602218370461602
    URL

  • 1-C-3 木における最小費用b-辺支配集合問題(離散最適化(1))
    伊藤 健洋; 垣村 尚徳; 神山 直之; 小林 佑輔; 岡本 吉央
    公益社団法人日本オペレーションズ・リサーチ学会, 出版日 2015年03月26日, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2015巻, 掲載ページ 44-45, 日本語, 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.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., 一般社団法人情報処理学会, 出版日 2015年02月24日, 研究報告アルゴリズム（AL）, 2015巻, 2号, 掲載ページ 1-6, 英語, 0919-6072, 110009877668, AN1009593X
    URL

  • 境界上の重みの釣合せ (計算理論とアルゴリズムの新潮流)
    バルバ ルイス; 鄭 地園; カルフェル ジャン・ルー・ド; ドビンズ マイケル; フライシャー ルードルフ; 河村 彰星; コルマン マティアス; 岡本 吉央; パハ ヤーノシュ; 唐 淵; 徳山 豪; バードンスホト サンダー; 王 天豪
    京都大学, 出版日 2014年05月, 数理解析研究所講究録, 1894巻, 掲載ページ 45-52, 日本語, 1880-2818, 110009804829, AN00061013
    URL

  • Guest editorial: Selected papers from ISAAC 2011
    Takao Asano; Shin-Ichi Nakano; Yoshio Okamoto
    出版日 2013年09月, Algorithmica, 67巻, 1号, 掲載ページ 1-2, 英語, 0178-4617, 84879268935
    DOI URL

  • Computational complexity and an integer programming model of Shakashaka (コンピュテーション)
    ドメイン エリック・D; 岡本 吉央; 上原 隆平; 宇野 裕之
    パズル「シャカシャカ」は,有名な数独をはじめとする多くのペンシルパズルと同様,日本の出版社ニコリが普及させたパズルである.これまで「シャカシャカ」の計算複雑さは未解決であった.本稿ではまず「シャカシャカ」がNP完全であることを示す.次に「シャカシャカ」を整数計画問題として記述する.これを実装し,市販されている本の問題をIPソルバで解いた実験結果を示す.その結果,どの問題も1秒以内に解けた., 一般社団法人電子情報通信学会, 出版日 2013年04月24日, 電子情報通信学会技術研究報告 : 信学技報, 113巻, 14号, 掲載ページ 43-48, 英語, 0913-5685, 110009768472, AN10013152
    URL

  • GUEST EDITORS' FOREWORD
    Takao Asano; Shin-Ichi Nakano; Yoshio Okamoto
    出版日 2013年04月, INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 23巻, 2号, 掲載ページ 73-74, 英語, その他, 0218-1959, 1793-6357, WOS:000327447000001
    DOI URL

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

  • 費用2種類の施設配置ゲームの仁とシャープレイ値の計算について
    並河 雄紀; 岡本 吉央; 大舘 陽太
    施設配置ゲームは施設配置問題から生じる協力ゲームである．この問題では，施設配置問題において各顧客が協力関係を築いて費用の最小化を行うと見なし，最小化した費用を顧客間でどのように分け合うかを協力ゲーム理論の解概念に基づいて考える．しかし，実際にそのような解を計算しようとすると，計算量理論の意味で難しいことが多い．本稿では，施設配置ゲームの一種である容量制約なし施設配置ゲームについて議論する．具体的には，施設の数が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., 出版日 2013年02月22日, 研究報告アルゴリズム（AL）, 2013巻, 3号, 掲載ページ 1-8, 日本語, 110009550136, AN1009593X
    URL

  • 『計算機科学者のためのゲーム理論入門』シリーズ第4回 : メカニズムデザイン(応用編)
    横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
    本稿では，メカニズムデザイン(応用編)として，前回の基礎編に対して，現実からの要請にもとづく社会的に望ましい結果，もしくは設計者の目的を満たす結果，をもたらすための市場や制度をメカニズムとしてどう考えるかに焦点をあてる．まず，メカニズムデザイン理論における代表的な応用である，異なる種類の商品を同時に販売するためのオークション，いわゆる組合せオークションを，もっともよく知られているVickrey-Clarke-Grovesメカニズムを通して説明する．次に，従来は考えられていなかった課題を解決するためのメカニズムをどのように設計するかを解説するために，架空名義入札を取り上げる．加えて，メカニズムデザイン理論のよく知られた実践例である，検索連動型広告オークションとマッチングメカニズムの主要な結果に関して述べる．, 日本ソフトウェア科学会, 出版日 2013年01月25日, コンピュータソフトウェア, 30巻, 1号, 掲載ページ 34-52, 日本語, 0289-6540, 10031138249
  • 協力ゲーム
    横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
    日本ソフトウェア科学会 ; 1984-, 出版日 2013年, コンピュータソフトウェア, 30巻, 2号, 掲載ページ 33-51, 英語, 0289-6540, 10031151473, 84883333397
    DOI URL

  • 『計算機科学者のためのゲーム理論入門』シリーズ第5回 協力ゲーム
    横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
    本稿では，ゲーム理論の主要領域の1つである協力ゲームについて解説する．協力ゲームは，主に2つの研究領域からなる．1つは，提携内のプレイヤ間で，協力によって得られた利益をどのように分配するかである．本編では，解概念と呼ばれる，協力的なエージェント間で利得を配分する望ましい方法について概説する．古典的な協力ゲーム理論では，コア，シャプレイ値，仁など，さまざまな解概念が提案されている．これらの解概念によって与えられる利得の配分を求めるアルゴリズムと計算量について考察する．2つ目は，全体提携が最適ではない場合，プレイヤがどのような協力関係(提携)を形成するかである．これは，提携構造形成問題(CSG)と呼ばれる．本編では，CSGを効率的に解く制約付き最適化アルゴリズムを紹介する．また，本編ではゲームの簡潔表現法を利用することで解概念やCSGに関する問題を効率的に解くことができるため，協力ゲームの簡潔な記述方法を概説する．, 日本ソフトウェア科学会, 出版日 2013年, コンピュータ ソフトウェア, 30巻, 2号, 掲載ページ 2_33-2_51, 日本語, 0289-6540, 130004892257
  • メカニズムデザイン(基礎編)
    横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
    本稿では，メカニズムデザイン(基礎編)として，メカニズムデザイン理論について概説する．メカニズムデザイン理論は不完備情報ゲームの枠組みを用いて，自身の利得の最大化を目指して行動するプレイヤの集団が，あるルール(メカニズム)の元でどのように振る舞うかを分析すると共に，どのようにメカニズムを設計すれば社会的に望ましい結果，もしくは設計者の目的を満たす結果を達成できるかを扱う理論である．本稿では，まずメカニズムデザインの基礎となる不完備情報ゲームを説明する．そして，メカニズムデザインの代表的な適用例であるオークションに即して，メカニズムデザインの考え方，およびただ1つの商品を販売するオークションにおけるメカニズムデザイン理論の主要結果を概説する．, 日本ソフトウェア科学会, 出版日 2012年10月25日, コンピュータソフトウェア, 29巻, 4号, 掲載ページ 15-31, 日本語, 0289-6540, 10031077886
  • 施設配置ゲームにおける仁・シャープレイ値の計算について
    並河 雄紀; 岡本 吉央; 大舘 陽太
    施設配置ゲームは施設配置問題から生じる協力ゲーム的問題である.この問題では,施設配置問題において各顧客が協力関係を築いて費用の最小化を行うと見なし,最小化した費用を顧客間でどのように分け合うかを協力ゲーム理論の解概念に基づいて考える.しかし,実際にそのような解を計算しようとすると,計算量理論の意味で難しいことが多い.本稿では,施設配置ゲームの一種である容量制約なし施設配置ゲームについて議論する.具体的には,施設の数が2個かつ費用が2種類の場合に,凸ゲームと呼ばれる良い性質を持つクラスに属するための必要十分条件を示す.さらに,一般の容量制約なし施設配置ゲームにおいて,仁とシャープレイ値が一致する例を示す., 一般社団法人電子情報通信学会, 出版日 2012年10月24日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 112巻, 272号, 掲載ページ 25-32, 日本語, 0913-5685, 110009636909, AN10013152
    URL

  • 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法
    清見 礼; 岡本 吉央; 斎藤 寿樹
    不完全なデータが与えられたときに,形質に基づいて系統樹を復元する問題を研究する.より正確には,形質が二値であり,有向完全系統樹の仮定が成り立つ場合に,ある種に対してある形質の状態がデータとして失われている状況を考える.本研究の目的は失われたデータを補完したときに得られる完全系統樹をすべて列挙するための効率的アルゴリズムを設計することである.単純な分枝限定アルゴリズム(B&B)は理論的に良い計算量を持つが,ゼロサプレス型二分決定グラフ(ZDD)に基づく別の方法を提案する.ランダム生成されたデータに対する実験では,ZDDに基づく手法がB&Bよりも優れた結果を示した.また,与えられた不完全データと矛盾しない完全系統樹の数を計算する問題が#P完全であることを示し,すなわち,効率的標本抽出が難しいことの傍証を与える., 一般社団法人電子情報通信学会, 出版日 2012年06月14日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 112巻, 93号, 掲載ページ 17-24, 英語, 0913-5685, 110009588447, AN10013152
    URL

  • 列挙の基本と基礎的なアルゴリズム
    岡本 吉央
    列挙問題とは,与えられた条件を満たすものを漏れなく,重複なく出力する問題である.本稿では,列挙問題を解くためのアルゴリズム設計技法として基礎的なものを紹介する.まず,列挙アルゴリズムの効率の良さの測り方を導入する.その後で,部分集合列挙問題を例題として,分割法,グレイコード,逆探索法という三つの設計技法を紹介する.最後に,効率の良い列挙アルゴリズムを設計することが難しい列挙問題とその理由について言及する., 一般社団法人電子情報通信学会, 出版日 2012年06月01日, 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers, 95巻, 6号, 掲載ページ 477-483, 日本語, 0913-5693, 110009457693, AN1001339X
    URL

  • 『計算機科学者のためのゲーム理論入門』シリーズについて
    横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
    日本ソフトウェア科学会, 出版日 2012年04月25日, コンピュータソフトウェア, 29巻, 2号, 掲載ページ 65-68, 日本語, 0289-6540, 10030311272
  • 非協力ゲーム(基礎編)
    横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
    本稿では，ゲーム理論の基礎となる標準形の非協力ゲームについて概説する．標準形の非協力ゲームでは，複数のプレイヤが，自身の利得の最大化を目指して，独立かつ同時に行動を選択する．各プレイヤの利得は，自身の行動と他のプレイヤの行動の組合せにより決定される．非協力ゲームの帰結を予測するために，様々な均衡概念が提案されている．本稿では，標準形の非協力ゲームの基礎となる用語と均衡概念について概説する．また，単純に標準形の非協力ゲームを記述した場合，その記述量はプレイヤの数に対して指数的に増加する．本編では，ゲームの簡潔な記述方法であるグラフィカルゲームと混雑ゲーム，およびこれらのゲームにおいて均衡を計算するためのアルゴリズム/計算量について概説する．, 日本ソフトウェア科学会, 出版日 2012年04月25日, コンピュータソフトウェア, 29巻, 2号, 掲載ページ 69-84, 日本語, 0289-6540, 10030311279
  • Special Issue: Selected Papers from the 21st Annual International Symposium on Algorithms and Computation FOREWORD
    Otfried Cheong; Yoshio Okamoto
    出版日 2012年02月, INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS, 22巻, 1号, 掲載ページ 1-2, 英語, その他, 0218-1959, WOS:000308707000001
    DOI URL

  • 非協力ゲーム(発展編)
    横尾 真; 岩崎 敦; 櫻井 祐子; 岡本 吉央
    本編では非協力ゲーム(発展編)として，非協力ゲームの均衡概念で最も重要なものであるナッシュ均衡について詳しく述べる．2人ゼロサム標準形ゲームでは，プレイヤが選択可能な純粋戦略の個数に関する多項式時間でナッシュ均衡を計算できる．しかしながら，プレイヤが交互に行動を繰り返し選択するような複雑なゲームでは純粋戦略の個数が膨大となる．本編では，このような複雑な2人ゼロサムゲームの均衡を計算する例として，ポーカー等のカードゲームにおいてナッシュ均衡を計算するアルゴリズムを紹介する．一方，一般の有限2人標準形ゲームでは，ナッシュ均衡が多項式時間で計算可能かどうかが分かっていない．しかしながら，ナッシュ均衡の存在自体は証明されているので，PやNPのような判定問題に関する概念は，ナッシュ均衡計算問題の難しさを議論するためには適切ではない．本編では，ナッシュ均衡計算問題の難しさを議論する際に有用な問題のクラスであるPPAD，およびPPAD完全性について解説する．, 日本ソフトウェア科学会, 出版日 2012年, コンピュータ ソフトウェア, 29巻, 3号, 掲載ページ 3_39-3_53, 日本語, 0289-6540, 130004549284
  • Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)
    Okamoto Yoshio; Otachi Yota; Uehara Ryuhei; UNO TAKEAKI
    一般社団法人電子情報通信学会, 出版日 2011年08月30日, 電子情報通信学会技術研究報告. COMP, コンピュテーション, 111巻, 195号, 掲載ページ 31-38, 英語, 0913-5685, 110008900047, AN10013152
    URL

  • 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
    出版日 2011年02月28日, 研究報告アルゴリズム（AL）, 2011巻, 1号, 掲載ページ 1-8, 英語, 110008583076, AN1009593X
    URL

  • Preface
    Takao Asano; Shin-Ichi Nakano; Yoshio Okamoto; Osamu Watanabe
    出版日 2011年, Lecture Notes in Computer Science, 7074巻, 英語, その他, 0302-9743, 84055193956
    DOI URL

  • 絵画的迷路の作り方 (理論計算機科学の深化と応用)
    岡本 吉央; 上原 隆平
    京都大学, 出版日 2009年05月, 数理解析研究所講究録, 1649巻, 掲載ページ 58-65, 日本語, 1880-2818, 110007105293, AN00061013
    URL

  • 2-F-5 多目的最適化への列挙アルゴリズム理論からのアプローチ(数理計画(1))
    岡本 吉央; 宇野 毅明
    公益社団法人日本オペレーションズ・リサーチ学会, 出版日 2006年03月14日, 日本オペレーションズ・リサーチ学会春季研究発表会アブストラクト集, 2006巻, 掲載ページ 212-213, 日本語, 110006168732, AN00351206
  • 第4回 離散最適化と協力ゲーム(2)
    毛利 裕昭; 岡本 吉央
    公益社団法人日本オペレーションズ・リサーチ学会, 出版日 2003年02月01日, オペレーションズ・リサーチ : 経営の科学 = [O]perations research as a management science [r]esearch, 48巻, 2号, 掲載ページ 114-120, 日本語, 0030-3674, 110001183690, AN00364999
    URL

書籍等出版物

  • 応用数理ハンドブック
    岡本吉央
    事典・辞書, 日本語, 共著, 離散システム (近似アルゴリズム), 朝倉書店, 出版日 2013年10月25日
  • 離散体積計算による組合せ論入門
    岡本吉央
    日本語, 単訳, シュプリンガー・ジャパン, 出版日 2010年
  • 離散数学のすすめ
    日本語, 共著, 第3章「平面上の点集合から見た離散数学」, 現代数学社, 出版日 2010年
  • Encyclopedia of Algorithms
    英語, 共著, Traveling Sales Person with Few Inner Points, Springer, 出版日 2008年
  • 離散幾何学講義
    岡本吉央
    日本語, 単訳, シュプリンガー・フェアラーク東京, 出版日 2005年
  • 凸多面体の数学
    八森正泰; 岡本吉央
    日本語, 共訳, シュプリンガー・フェアラーク東京, 出版日 2003年

担当経験のある科目_授業

  • Theory of Computation
    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
  • 離散数学
    電気通信大学
  • 離散数理工学
    電気通信大学
  • キャリア教育演習
    電気通信大学
  • キャリア教育演習
    電気通信大学
  • 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
  • 数理解析
    電気通信大学

所属学協会

  • 日本オペレーションズ・リサーチ学会
  • Mathematical Optimization Society
  • European Association for Theoretical Computer Science
  • LAシンポジウム
  • 電子情報通信学会

共同研究・競争的資金等の研究課題

  • 幾何学的に構成されるグラフに対する積構造定理と統一的アルゴリズム設計法
    岡本 吉央
    日本学術振興会, 科学研究費助成事業, 電気通信大学, 基盤研究(C), 23K10982
    研究期間 2023年04月01日 - 2026年03月31日
  • 組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合
    伊藤 健洋; 川原 純; 岡本 吉央; 鈴木 顕
    日本学術振興会, 科学研究費助成事業, 東北大学, 学術変革領域研究(B), 本研究は，研究領域「組合せ遷移の展開に向けた計算機科学・工学・数学によるアプローチの融合」の総括班であり，その目的は「班間連携の促進」と「外部への広報活動」の大きく２つである．これらを実現するために，下記の通り活動を行った． まず，本年度の領域会議を2020年10月30日と2021年3月23日の２回完全オンラインにて開催した．１０月の領域会議では，本研究領域の全体像をメンバーらと再確認した．３月の領域会議では，班間連携を促進するためにも，各計画研究班の半年間の研究動向を報告し合い，研究討論を行った．また，１０月，３月の領域会議ともに，同日に一般公開のシンポジウムも併催した．１０月の公開シンポジウムは，キックオフミーティングと銘打って，本研究領域の目的と計画を中心に解説した．３月の公開シンポジウムでは，招待講演も企画した． さらにオンラインでは，組合せ遷移のセミナー・勉強会を継続して行った．2020年度中には７回開催し，それらは全て一般公開している．セミナー・勉強会は，本研究領域のメンバーが自身の研究を紹介することで，その背景分野を互いに勉強し合い，班間連携の促進につなげることを目的としている． この他にもアウトリーチ活動として，本研究領域Webサイトの開設，ニュースレター創刊号の発行，電気通信大学主催の産学官連携イベントでの発表などを行った． また，大容量メモリ搭載計算サーバを設置し，本研究領域のメンバーが利用できるように環境整備を行った．, 20H05792
    研究期間 2020年10月 - 2023年03月
  • 数学アプローチによる組合せ遷移の展開：活用事例を手がかりとして新解法へ
    研究代表者
    研究期間 2020年10月 - 2023年03月
  • 大規模配位空間の最適化理論：離散構造論の視点を中心にして
    基盤研究(C)一般, 研究代表者
    研究期間 2020年04月 - 2023年03月
  • パラメータ化計算量による幾何近似アルゴリズム
    JSPS, 二国間事業共同研究 (インド (DST) との共同研究)
    研究期間 2019年 - 2021年
  • 内在構造に基づく大規模グラフの高速処理とその理論基盤構築
    栢森情報科学振興財団, 研究助成
    研究期間 2017年01月 - 2018年12月
  • 計算幾何学と計算トポロジーが拓く新時代データ解析の理論基盤
    基盤研究(C)一般, 研究代表者
    研究期間 2015年 - 2017年
  • 持続可能な発展のための資源配分メカニズム設計理論の構築
    基盤研究(S), 研究分担者
    研究期間 2012年 - 2016年
  • 最適化技法との融合による計算限界解析法の深化
    新学術領域研究（研究課題提案型）, 研究分担者, 新学術領域研究（研究領域提案型）
    研究期間 2012年 - 2016年
  • 厳密計算における信頼性とその理論保証のための数理的アプローチ
    若手研究(B), 研究代表者
    研究期間 2012年 - 2014年
  • 大規模なセンサネットワーク位置推定問題の数値解法に関する研究
    小島 政和; 岡本 吉央; 三好 直人; 山下 真; 藤澤 克樹
    日本学術振興会, 科学研究費助成事業, 東京工業大学, 基盤研究(B)一般, 研究分担者, センサネットワークは,環境モニタリング,構造物管理,交通制御などのさまざまな分野で使われている.アンカーと呼ばれるその位置が既知のm個のセンサとネットワーク上で隣接するセンサ間の距離の情報からその位置が未知のn個のセンサの位置を推定する問題は最も基本的で重要な問題の1つである.理論的にはNP困難な難しい問題として知られており,さまざまな分野で研究が行われている.この研究課題では,センサネットワーク位置推定問題に対する半正定値計画緩和を中心に研究を進めた.半正定値計画緩和は精度の良い推定位置を生成することが知られているが,センサネットワーク位置推定問題の規模の増加に伴って,計算コストが急速に増加する欠点を有している.この欠点を解消するためにネットワークの構造的な疎性の有効利用および半正定値計画問題を解く主双対内点法ソフトウェアSDPAの高速化をおこなった.この研究課題の主たる研究成果として大規模な問題を高速に解くソフトウェアパッケージSFSDPを開発・公開した., 22310089
    研究期間 2010年 - 2012年
  • 多面体的組合せ論に基づく数え上げアルゴリズム設計理論の構築
    岡本 吉央
    日本学術振興会, 科学研究費助成事業, 若手研究(B), 研究代表者, グラフに対する数え上げ問題,離散幾何・計算幾何に関する数え上げ問題,そして,最適化問題に対するそれらの応用に関して研究成果を得た.例を挙げると,グラフの部分構造である支配集合を数え上げる問題に対して,グラフクラスの観点からその困難性を明らかにした.また,多角形領域における距離関数最大化問題の局所最適解を列挙するアルゴリズムを開発し,そこから大域最適解が多項式時間で見つけられることを示した.これらを査読付き英文論文誌,ならびに,査読付き国際会議にて発表した., 21700009
    研究期間 2009年 - 2011年
  • グラフ・ネットワーク上のゲーム理論に対するアルゴリズム理論的厳密アプローチ
    岡本 吉央
    日本学術振興会, 科学研究費助成事業, 若手研究(B), 研究代表者, グラフ・ネットワークに関わる協力ゲーム理論について,アルゴリズム理論・計算理論の観点から精緻な議論を行った.特に,最小彩色ゲームと呼ばれる費用分担問題に対して,今までに提案された公平な費用分担の中のいくつかが効率よく計算できることを示した.それに加えて,コア安定性問題に対する計算量理論的な解析も行った.さらに,最小費用全域木ゲームと呼ばれる費用分担問題に対して,公平費用分担が効率よく計算できるための十分条件である劣モジュラ性を満たす場合の考察をした., 18710130
    研究期間 2006年 - 2008年
  • 実践的な列挙アルゴリズムの理論構築
    宇野 毅明; 中野 眞一; 松井 泰子; 岡本 吉央; 清見 礼
    日本学術振興会, 科学研究費助成事業, 国立情報学研究所, 特定領域研究（計画）, 研究分担者, 研究分担者となったのは2004年度から．, 16092227
    研究期間 2004年 - 2007年

社会貢献活動

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

学術貢献活動

  • 31st International Computing and Combinatorics Conference (COCOON 2025)
    査読, 実施期間 2025年03月 - 2025年05月
  • 19th International Conference and Workshops on Algorithms and Computation (WALCOM 2025)
    査読, 実施期間 2024年09月 - 2024年11月