Degree

• 教養学士（東京大学 1999-03）
• 修士（学術）（東京大学 2001-03）
• Ph.D.（ETH Zurich 2005-03）

Research History

Education

Awards

• 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）

Others

Papers

• 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]
• Counting the Number of Matchings in Chordal and Chordal Bipartite Graph Classes（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）

Misc

• ネットワーク型交渉ゲームの安定化アルゴリズム（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]
• Weight Balancing on Boundaries and Skeletons (New Streams of Computation Theory and Algorithms)（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]
• On computing the nucleolus and the Shapley value of facility location games with two cost values（2013-02-22） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Game Theory for Computer Scientist : Mechanism Design (Advanced)（2013-01-25） [CiNii Research (CiNii Articles)]
• Game Theory for Computer Scientists - Cooperative Games（2013） [CiNii Research (CiNii Articles)] [DOI]
• Game Theory for Computer Scientists — Cooperative Games —（2013） [CiNii Research (CiNii Articles)]
• Game Theory for Computer Scientists : Mechanism Design (Basic)（2012-10-25） [CiNii Research (CiNii Articles)]
• On Computing the Nucleolus and the Shapley Value of Facility Location Games（2012-10-24） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Efficient Enumeration of the Directed Binary Perfect Phylogenies from Incomplete Data（2012-06-14） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Enumeration Fundamentals and Basic Algorithms（2012-06-01） [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Introduction of Game Theory for Computer Scientists（2012-04-25） [CiNii Research (CiNii Articles)]
• Game Theory for Computer Scientists : Noncooperative Games (Basic Theory)（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]
• Game Theory for Computer Scientists —Noncooperative Games (Advanced)—（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]
• How to make a picturesque maze (Theoretical Computer Science and Its Applications)（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]

Presentations

Books and Other Publications

• 応用数理ハンドブック（2013-10-25）
• Computing the Continuous Discretely: Integer-Point Enumeration in Polyhedra（2010）
• 離散数学のすすめ（2010）
• Encyclopedia of Algorithms（2008）
• Lectures on Discrete Geometry（2005）
• Lectures on Polytopes（2003）

Works

Research Projects

Media Coverage

Industrial Property Rights

Professional Memberships

• 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

Committee Memberships

Teaching Experience

• 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
• 数理解析

Social Contribution

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

Academic Contribution

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