学位

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

経歴

学歴

受賞

• Outstanding Reviewer Award of SoCG 2025（2025-06）
• 2023年度コンピュータサイエンス領域功績賞（2024-01）
• 日本オペレーションズ・リサーチ学会フェロー（2022-03）
• 船井ベストペーパー賞（2021-09）
• 日本オペレーションズ・リサーチ学会第10回研究賞（2020-09）
• 日本ソフトウェア科学会第5回解説論文賞（2015）
• 日本オペレーションズ・リサーチ学会研究賞奨励賞（2012）
• 8th EATCS/LA Presentation Award（2010）
• Editors' Choice 2003, Discrete Applied Mathematics（2004）

その他

論文

• The Solitaire Clobber game and the correducibility of k-connected graphs（2025-05） [DOI]
• Reforming an Envy-Free Matching（2025-04） [DOI]
• Reconfiguration of colorings in triangulations of the sphere（2025-04） [DOI]
• Rerouting Planar Curves and Disjoint Paths（2025-03） [DOI] [Othres link]
• Minimum separator reconfiguration（2024-12） [DOI]
• CoRe Challenge 2022/2023: Empirical Evaluations for Independent Set Reconfiguration Problems (Extended Abstract)（2024-06-01） [DOI] [Othres link]
• Minimum Separator Reconfiguration（2023-12） [DOI]
• On reachable assignments under dichotomous preferences（2023-11） [DOI]
• Algorithmic Theory of Qubit Routing（2023-07） [DOI] [DBLP] [Othres link] [Othres link]
• Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra（2023-07） [DOI] [DBLP] [Othres link] [Othres link]
• Rerouting Planar Curves and Disjoint Paths（2023-07） [DOI] [DBLP] [Othres link] [Othres link]
• Reconfiguration of Colorings in Triangulations of the Sphere（2023-06） [DOI] [DBLP] [Othres link] [Othres link]
• Algorithmic Theory of Qubit Routing（2023-05） [DOI] [DBLP] [Othres link]
• Hardness of Finding Combinatorial Shortest Paths on Graph Associahedra（2023-04） [DOI] [DBLP] [Othres link]
• Monotone Edge Flips to an Orientation of Maximum Edge-Connectivity à la Nash-Williams（2023-01-31） [DOI] [Othres link]
• Graphs with large total angular resolution（2023-01） [DOI]
• On Reachable Assignments Under Dichotomous Preferences（2022-11） [DOI] [Othres link]
• Rerouting Planar Curves and Disjoint Paths（2022-10） [DOI] [DBLP] [Othres link]
• Core Challenge 2022: Solver and Graph Descriptions（2022-08） [DOI] [DBLP] [Othres link]
• Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds（2022-06）
• Weight balancing on boundaries（2022-06） [DOI]
• Reforming an Envy-Free Matching（2022-06） [DBLP] [Othres link] [Othres link] [Othres link]
• Shortest Reconfiguration of Perfect Matchings via Alternating Cycles（2022-06） [DOI]
• A Parameterized View to the Robust Recoverable Base Problem of Matroids Under Structural Uncertainty（2022-05） [DOI]
• Linear-Time Recognition of Double-Threshold Graphs.（2022） [DOI] [DBLP] [Othres link]
• Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams（2022-01） [DOI] [DBLP] [Othres link] [Othres link]
• Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams（2021-10） [DBLP] [Othres link] [Othres link]
• Submodular reassignment problem for reallocating agents to tasks with synergy effects（2021-02） [DOI]
• ClusterSets: Optimizing planar clusters in categorical point data（2021）
• Algorithms for gerrymandering over graphs.（2021） [DOI] [DBLP] [Othres link]
• Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain（2021）
• Algorithmic enumeration of surrounding polygons（2020-04） [DOI]
• Balanced line separators of unit disk graphs（2020-01-01） [DOI]
• Linear-Time Recognition of Double-Threshold Graphs（2020） [DOI] [DBLP] [Othres link] [Othres link]
• Subgraph Isomorphism on Graph Classes that Exclude a Substructure（2019） [DBLP] [DOI] [Othres link] [Othres link]
• Graphs with Large Total Angular Resolution（2019）
• Variants of the Segment Number of a Graph（2019）
• Shortest Reconfiguration of Perfect Matchings via Alternating Cycles.（2019） [DOI] [DBLP] [DBLP] [DBLP]
• Computing the Geodesic Centers of a Polygonal Domain（2019）
• Minimum-Cost b-Edge Dominating Sets on Trees.（2019） [DOI] [DBLP] [DBLP]
• Sequentially Swapping Colored Tokens on Graphs（2019） [DOI] [DBLP] [Othres link]
• Reconfiguration of maximum-weight b-matchings in a graph.（2019） [DOI] [DBLP] [DBLP]
• Area bounds of rectilinear polygons realized by angle sequences（2019）
• Algorithms for Gerrymandering over Graphs.（2019） [DBLP] [Othres link] [DBLP] [DBLP]
• Shortest Reconfiguration of Perfect Matchings via Alternating Cycles.（2019） [DBLP] [arXiv] [DBLP]
• Tight Approximability of the Server Allocation Problem for Real-Time Applications（2018） [DOI] [Othres link]
• Exact Algorithms for the Max-Min Dispersion Problem.（2018） [DOI] [DBLP] [DBLP] [DBLP] [Othres link]
• Computational Complexity of Robot Arm Simulation Problems（2018） [DOI] [DBLP] [Othres link] [Othres link]
• Orthogonal and Smooth Orthogonal Layouts of 1-Planar Graphs with Low Edge Complexity（2018）
• Folding free-space diagrams: Computing the Fréchet distance between 1-dimensional curves（2017-06-01） [DOI]
• Efficient stabilization of cooperative matching games（2017-05） [DOI] [Web of Scientce]
• Computing the L-1 Geodesic Diameter and Center of a Polygonal Domain（2017-04） [DOI] [Web of Scientce]
• General Constructions of Rational Secret Sharing with Expected Constant-Round Reconstruction（2017-04） [DOI] [Web of Scientce]
• Sequentially Swapping Colored Tokens on Graphs（2017） [DOI] [Web of Scientce]
• Sankaku-Tori: An Old Western-Japanese Game Played on a Point Set（2017） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Balanced line separators of unit disk graphs（2017） [DOI]
• Reconfiguration of maximum-weight b-matchings in a graph（2017） [DOI]
• Extended formulations for sparsity matroids（2016-07） [DOI] [Web of Scientce]
• Computational Complexity of Sequential Token Swapping Problem (コンピュテーション)（2016-06-24） [CiNii Research (CiNii Articles)]
• シーケンシャルな交換による色付きトークン整列問題の計算複雑さ（2016-06）
• On Problems as Hard as CNF-SAT（2016-06） [DOI] [Web of Scientce]
• A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares（2016-01） [DOI] [Web of Scientce]
• On the treewidth of toroidal grids（2016-01） [DOI] [Web of Scientce]
• Efficient Stabilization of Cooperative Matching Games（2016）
• Approximation and Hardness of Token Swapping（2016）
• Computing the L-1 geodesic diameter and center of a simple polygon in linear time（2015-08） [DOI] [Web of Scientce]
• Free Edge Lengths in Plane Graphs（2015-07） [DOI] [Web of Scientce]
• Swapping labeled tokens on graphs（2015-06） [DOI] [Web of Scientce]
• Polynomial-time approximability of the k-Sink Location problem.（2015） [DBLP] [Othres link]
• A 4.31-approximation for the geometric unique coverage problem on unit disks（2014-08） [DOI] [Web of Scientce]
• Computational Complexity and an Integer Programming Model of Shakashaka（2014-06） [DOI] [Web of Scientce]
• Submodularity of minimum-cost spanning tree games（2014-05） [DOI] [Web of Scientce]
• Approximating the path-distance-width for AT-free graphs and graphs in related classes（2014-05） [DOI] [Web of Scientce]
• グラフ上のラベル付きトークン整列問題（2014-04）
• Computing the geodesic centers of a polygonal domain（2014）
• Computing the L-1 Geodesic Diameter and Center of a Simple Polygon in Linear Time（2014） [DOI] [Web of Scientce]
• Semantic Word Cloud Representations: Hardness and Approximation Algorithms（2014） [Web of Scientce]
• Free edge lengths in plane graphs（2014） [DOI]
• Weight balancing on boundaries and Skeletons（2014） [DOI]
• Sankaku-Tori: An Old Western-Japanese Game Played on a Point Set（2014） [Web of Scientce]
• Swapping Labeled Tokens on Graphs（2014） [Web of Scientce]
• Minimum-Cost b-Edge Dominating Sets on Trees（2014） [DOI] [Web of Scientce]
• The Geodesic Diameter of Polygonal Domains（2013-09） [DOI] [Web of Scientce]
• The complexity of the stamp folding problem（2013-07） [DOI] [Web of Scientce]
• Exact and fixed-parameter algorithms for metro-line crossing minimization problems（2013）
• Querying two boundary points for shortest paths in a polygonal domain（2012-08） [DOI] [Web of Scientce]
• Vertex angle and crossing angle resolution of leveled tree drawings（2012-08） [DOI] [Web of Scientce]
• Reverse preferential spread in complex networks（2012-08） [DOI] [Web of Scientce]
• 単位正方形上の一意被覆問題に対する近似アルゴリズム（2012-06）
• Guest editors' foreword（2012-02） [DOI]
• Drawing (Complete) Binary Tanglegrams Hardness, Approximation, Fixed-Parameter Tractability（2012-02） [DOI] [Web of Scientce]
• Game Theory for Computer Scientists -Noncoop-erative Games (Advanced)-.（2012） [DOI]
• Efficient enumeration of the directed binary perfect phylogenies from incomplete data（2012） [DOI]
• A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares（2012） [DOI]
• On Problems as Hard as CNF-SAT（2012） [DOI] [Web of Scientce]
• Minimum and maximum against k lies（2012）
• On bipartite powers of bigraphs（2012） [Web of Scientce]
• A 4.31-Approximation for the Geometric Unique Coverage Problem on Unit Disks（2012） [Web of Scientce]
• Universal Point Subsets for Planar Graphs（2012） [Web of Scientce]
• Area Bounds of Rectilinear Polygons Realized by Angle Sequences（2012） [Web of Scientce]
• The t-pebbling number is eventually linear in t（2011-07） [Web of Scientce]
• A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization（2011-04） [DOI] [Web of Scientce]
• Adaptive Algorithms for Planar Convex Hull Problems（2011-02） [DOI] [Web of Scientce]
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem（2011） [DOI]
• Submodular fractional programming for balanced clustering（2011-01） [DOI] [Web of Scientce]
• Approximability of the Path-Distance-Width for AT-free Graphs（2011） [Web of Scientce]
• Dominating set counting in graph classes（2011） [DOI] [DBLP] [Othres link] [Othres link]
• Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem（2011） [Web of Scientce]
• Improved Bounds for Wireless Localization（2010-07） [DOI] [Web of Scientce]
• On listing, sampling, and counting the chordal graphs with edge constraints（2010-06） [DOI] [Web of Scientce]
• 支配集合数え上げ問題とグラフクラス（2010-04）
• A tight lower bound for convexly independent subsets of the Minkowski sums of planar point sets（2010）
• The Geodesic Diameter of Polygonal Domains（2010） [Web of Scientce]
• Adaptive Algorithms for Planar Convex Hull Problems（2010） [Web of Scientce]
• Minimum and Maximum against k Lies（2010） [Web of Scientce]
• Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes（2010） [Web of Scientce]
• Untangling a Planar Graph（2009-12） [DOI] [Web of Scientce]
• The Holt-Klee condition for oriented matroids（2009-11） [DOI] [Web of Scientce]
• 弦グラフおよび弦二部グラフのクラスにおけるマッチングの数え上げ（2009-06）
• FAST EXPONENTIAL-TIME ALGORITHMS FOR THE FOREST COUNTING AND THE TUTTE POLYNOMIAL COMPUTATION IN GRAPH CLASSES（2009-02） [Web of Scientce]
• How to make a picturesque maze.（2009） [DBLP] [Othres link] [Othres link]
• Querying Two Boundary Points for Shortest Paths in a Polygonal Domain (Extended Abstract)（2009） [Web of Scientce]
• Drawing (Complete) Binary Tanglegrams Hardness, Approximation, Fixed-Parameter Tractability（2009） [Web of Scientce]
• Local topology of the free complex of a two-dimensional generalized convex shelling（2008-09） [DOI] [Web of Scientce]
• Fair cost allocations under conflicts - a game-theoretic point of view（2008-02） [DOI] [Web of Scientce]
• コーダルサンドイッチの列挙, ランダム生成, 数え上げについて（2008）
• Counting the number of independent sets in chordal graphs（2008） [DOI] [CiNii Research (CiNii Articles)] [Othres link]
• Improved bounds for wireless localization（2008） [Web of Scientce]
• On listing, sampling, and counting the chordal graphs with edge constraints（2008） [Web of Scientce]
• Moving vertices to make drawings plane（2008） [Web of Scientce]
• Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs（2007-10） [DOI] [Web of Scientce]
• Matroid representation of clique complexes（2007-09） [DOI] [Web of Scientce]
• A polynomial-time-delay and polynomial-space algorithm for enumeration problems in multi-criteria optimization（2007） [Web of Scientce]
• Fast exponential-time algorithms for the forest counting in graph classes（2007） [CiNii Research (CiNii Articles)]
• The even outdegree conjecture for acyclic PLCP-cubes in dimension five（2006-08） [DOI] [Web of Scientce]
• The minimum weight triangulation problem with few inner points（2006-07） [DOI] [Web of Scientce]
• Core stability of minimum coloring games（2006-05） [DOI] [Web of Scientce]
• 多目的最適化問題への列挙アルゴリズム理論からのアプローチ（2006-03）
• The traveling salesman problem with few inner points（2006-01） [DOI] [Web of Scientce]
• The affine representation theorem for abstract convex geometries（2005-02） [DOI] [Web of Scientce]
• Linear-time counting algorithms for independent sets in chordal graphs（2005） [Web of Scientce]
• Counting the Independent Sets of a Chordal Graph（2004-07）
• Traveling salesman games with the Monge property（2004-04） [DOI] [Web of Scientce]
• Core stability of minimum coloring games（2004） [Web of Scientce]
• The minimum weight triangulation problem with few inner points（2004） [Web of Scientce]
• The traveling salesman problem with few inner points（2004） [Web of Scientce]
• Submodularity of some classes of the combinatorial optimization games（2003-10） [DOI] [Web of Scientce]
• The forbidden minor characterization of line-search antimatroids of rooted digraphs（2003-09） [Web of Scientce]
• A greedy algorithm for convex geometries（2003-09） [Web of Scientce]
• Fair cost allocations under conflicts - A game-theoretic point of view（2003） [Web of Scientce]
• Greedy edge-disjoint paths in complete graphs（2003） [Web of Scientce]
• The free complex of a two-dimensional generalized convex shelling（2003）
• Matroid representation of clique complexes（2003） [Web of Scientce]
• Some properties of the core on convex geometries（2002）

その他業績

• ネットワーク型交渉ゲームの安定化アルゴリズム（2016-02-28） [J-GLOBAL] [Othres link]
• 1-C-3 木における最小費用b-辺支配集合問題(離散最適化(1))（2015-03-26） [CiNii Research (CiNii Articles)]
• Minimum-Cost b-Edge Dominating Sets on Trees（2015-02-24） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• 境界上の重みの釣合せ (計算理論とアルゴリズムの新潮流)（2014-05） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link] [Othres link]
• Guest editorial: Selected papers from ISAAC 2011（2013-09） [DOI]
• Computational complexity and an integer programming model of Shakashaka (コンピュテーション)（2013-04-24） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• GUEST EDITORS' FOREWORD（2013-04） [DOI] [Web of Scientce]
• グラフを通したパズル・ゲームの一般化（2013-03-01） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• 費用2種類の施設配置ゲームの仁とシャープレイ値の計算について（2013-02-22） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• 『計算機科学者のためのゲーム理論入門』シリーズ第4回 : メカニズムデザイン(応用編)（2013-01-25） [CiNii Research (CiNii Articles)]
• 協力ゲーム（2013） [CiNii Research (CiNii Articles)] [DOI]
• 『計算機科学者のためのゲーム理論入門』シリーズ第5回 協力ゲーム（2013） [CiNii Research (CiNii Articles)]
• メカニズムデザイン(基礎編)（2012-10-25） [CiNii Research (CiNii Articles)]
• 施設配置ゲームにおける仁・シャープレイ値の計算について（2012-10-24） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• 不完全データと矛盾しない有向二値完全系統樹を列挙する効率的手法（2012-06-14） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• 列挙の基本と基礎的なアルゴリズム（2012-06-01） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• 『計算機科学者のためのゲーム理論入門』シリーズについて（2012-04-25） [CiNii Research (CiNii Articles)]
• 非協力ゲーム(基礎編)（2012-04-25） [CiNii Research (CiNii Articles)]
• Special Issue: Selected Papers from the 21st Annual International Symposium on Algorithms and Computation FOREWORD（2012-02） [DOI] [Web of Scientce]
• 非協力ゲーム(発展編)（2012） [CiNii Research (CiNii Articles)]
• Hardness results and an exact exponential algorithm for the spanning tree congestion problem (コンピュテーション)（2011-08-30） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Approximating the path-distance-width for k-cocomparability graphs（2011-02-28） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Preface（2011） [DOI]
• 絵画的迷路の作り方 (理論計算機科学の深化と応用)（2009-05） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link] [Othres link]
• 2-F-5 多目的最適化への列挙アルゴリズム理論からのアプローチ(数理計画(1))（2006-03-14） [CiNii Research (CiNii Articles)] [CiNii Books]
• 第4回 離散最適化と協力ゲーム(2)（2003-02-01） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]

講演・口頭発表等

書籍等出版物

• 応用数理ハンドブック（2013-10-25）
• 離散体積計算による組合せ論入門（2010）
• 離散数学のすすめ（2010）
• Encyclopedia of Algorithms（2008）
• 離散幾何学講義（2005）
• 凸多面体の数学（2003）

作品等

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

メディア報道

産業財産権

所属学協会

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

委員歴

担当経験のある科目

• Theory of Computation
• 計算理論
• 情報・通信工学基礎
• 情報・通信工学基礎
• 情報・通信工学基礎
• Mathematical Information Science Laboratory IIB
• Mathematical Information Science Laboratory IIA
• 離散数学
• 離散数理工学
• キャリア教育演習
• キャリア教育演習
• Introduction to Science and Technology Studies II
• 科学技術社会論II
• Discrete Mathematical Engineering
• 離散数理工学
• Graphs and Networks
• グラフとネットワーク
• 最適化手法
• 最適化手法
• 数理科学特別講義VIII／数理科学特論8
• 数理科学特別講義VIII／数理科学特論8
• 情報数理科学特別講義D／情報数理科学特別講義H／情報数理科学特殊講義B
• 情報数理科学特別講義D／情報数理科学特別講義H／情報数理科学特殊講義B
• Graduate Course of Science and Technology on Communications
• 大学院総合コミュニケーション科学
• Information Engineering Laboratory
• 情報工学工房
• Graduate Technical English
• 大学院技術英語
• Mathematical Information Science Laboratory II A
• 情報数理工学実験第二A
• Discrete Mathematics
• 離散数学
• Foundation of Discrete Optimization
• 離散最適化基礎論
• Mathematical Information Science Laboratory II B
• 情報数理工学実験第二B
• Mathematical Analysis
• 数理解析

社会貢献活動

• 匠ガールプロジェクト2024「夏休みは電通大でラボ体験」

学術貢献活動

• 31st International Computing and Combinatorics Conference (COCOON 2025)
• 19th International Conference and Workshops on Algorithms and Computation (WALCOM 2025)