学位

• 博士（工学）(京都大学)

経歴

学歴

受賞

• フェロー（電子情報通信学会）

その他

論文

• Geodesic Paths Passing Through All Faces on A Polyhedron
• Numerically balanced dice on convex isohedra [ResearchMap] [ResearchMap]
• Multifold tiles of polyominoes and convex lattice polygons
• Computational complexity of flattening fixed-angle orthogonal chains
• Sublinear computation paradigm: constant-time algorithms and sublinear progressive algorithms
• Decrease and reset for power‐down [DOI] [Othres link] [Othres link]
• Turning Around and Around: Motion Planning through Thick and Thin Turnstiles [Othres link]
• Flat Folding a Strip with Parallel or Nonacute Zig-zag Creases with Mountain-Valley Assignment [DOI] [DBLP] [Othres link]
• K_3 edge cover problem in a wide sense [DOI] [DBLP] [Othres link]
• Twenty Years of Progress of $$\hbox {JCDCG}^3$$ [DOI] [Othres link] [Othres link]
• On the characterization of 1-sided error strongly-testable graph properties for bounded-degree graphs [DOI]
• Generalized shogi, chess, and xiangqui are constant-time testable
• Modulation-Adaptive Link-Disjoint Path Selection Model for 1+1 Protected Elastic Optical Networks [DOI] [DBLP] [Othres link]
• Preface for the Special Issue on the Project "Foundation of Innovative Algorithms for Big Data". [DOI] [DBLP] [Othres link]
• Cookie Clicker
• What graph properties are constant-time testable? --- dense graphs, sparse graphs, and complex networks
• Hyperfiniteness of real-world newtorks [DOI] [Othres link] [Othres link]
• Energy efficiency and renewable energy management with multi-state power-down system [DOI]
• A heuristic for state power down systems with few states [DOI]
• Bumpy pyramid folding [DOI]
• A much faster algorithm for finding a maximum clique with computational experiments [DOI]
• Unfolding and dissection of multiple cubes, tetrahedra, and doubly covered squares [DOI]
• Transforming graphs with the same graphic sequence [DOI]
• How to solve the cake-cutting problem in sublinear time [DOI]
• A Much Faster Branch-and-Bound Algorithm for Finding a Maximum Clique [DOI] [Web of Scientce]
• Folding a paper strip to minimize thickness [DOI]
• Every property is testable on a natural class of scale-free multigraphs
• Constant-time algorithms for complex networks
• Single-Player and Two-Player Buttons & Scissors Games [DOI] [Web of Scientce]
• Number of Ties and Undefeated Signs in a Generalized Janken [DOI] [Web of Scientce]
• Evaluation of Online Power-Down Algorithms [DOI] [Web of Scientce]
• Cannibal Animal Games: A new variant of Tic-Tac-Toe [DOI]
• Folding a Paper Strip to Minimizing Thickness [DOI] [CiNii Research (CiNii Articles)] [Othres link]
• Generalized shogi and chess are constant-time tastable
• Computational complexity of inverse word search problem
• Bumpy Pyramid Folding. [DBLP] [Othres link] [Othres link]
• Testing outerplanarity of bounded degree graphs
• Generalized River Crossing Problems [DOI]
• On computational complexity of graph inference from counting [DOI] [Scopus] [Scopus]
• Helly Numbers of Polyominoes [DOI]
• How to generalize janken - Rock-paper-scissors-king-flea [DOI]
• Property Testing on k-Vertex-Connectivity of Graphs [DOI] [Web of Scientce]
• An almost optimal algorithm for Winkler's sorting pairs in bins [DOI]
• Constant-time approximation algorithms for the knapsack problem [DOI]
• Algorithms and complexity of generalized river crossing problems [DOI]
• Constant-Time Algorithms for Sparsity Matroids [Web of Scientce]
• An online algorithm optimally self-tuning to congestion for power management problems [DOI]
• IMPROVED CONSTANT-TIME APPROXIMATION ALGORITHMS FOR MAXIMUM MATCHINGS AND OTHER OPTIMIZATION PROBLEMS [DOI] [Web of Scientce]
• Complexity of the stamp folding problem
• Constant-Time Approximation Algorithms for the Optimum Branching Problem on Sparse Graphs [DOI] [Web of Scientce]
• Helly numbers of polyominoes
• Testing Algorithms for (k, l)-Sparsity and (k, l)-Edge-Connected Orientability
• Arrangements of n Points whose Incident-Line-Numbers are at most n/2 [DOI] [Web of Scientce]
• Cannibal animal games: a new variant of tic-tac-toe
• PSPACE-completeness of the Weighted Poset Game [Web of Scientce]
• Making Polygons by Simple Folds and One Straight Cut [Web of Scientce]
• Complexity of the Stamp Folding Problem [Web of Scientce]
• Query-Number Preserving Reductions and Linear Lower Bounds for Testing [DOI] [Web of Scientce]
• TESTING k-EDGE-CONNECTIVITY OF DIGRAPHS [DOI] [Web of Scientce]
• Tractability and Intractability of Problems on Unit Disk Graphs Parameterized by Domain Area [Web of Scientce]
• Testing Outerplanarity of Bounded Degree Graphs [Web of Scientce]
• Enumeration of Isolated Cliques and Pseudo-Cliques [DOI] [Web of Scientce]
• Maximum-cover source location problems with objective edge-connectivity three [DOI] [Web of Scientce]
• The multi-commodity source location problems and the price of greed [DOI]
• An Improved Constant-Time Approximation Algorithm for Maximum Matchings [Web of Scientce]
• Inferring pedigree graphs from genetic distances [DOI] [Web of Scientce]
• Enumeration of Tsume-Shogi diagrams by the reverse method [DOI] [Web of Scientce]
• Multi-commodity source location problems and price of greed [Web of Scientce]
• Property testing on k-vertex-connectivity of graphs [Web of Scientce]
• Transforming Graphs with the Same Degree Sequence [Web of Scientce]
• Multi-commodity source location problems and price of greed [Web of Scientce]
• Snaky is a winner with one handicap [CiNii Research (CiNii Articles)]
• Winning ways of weighted poset games [DOI] [Web of Scientce]
• Semi-distance codes and Steiner systems [DOI] [Web of Scientce]
• Impossibility of transformation of vertex labeled simple graphs preserving the cut-size order [Web of Scientce]
• Infinite series of generalized Gosper space filling curves [Web of Scientce]
• Maximum-Cover Source-Location Problem with Objective Edge-Connectivity Three [DOI]
• Efficient methods for determining DNA probe orders [DOI] [J-GLOBAL] [Web of Scientce]
• Maximum-cover source-location problems [DOI] [Web of Scientce]
• ハラリイの一般化三並べ
• Efficient methods of determining DNA probe sequences
• Two equivalent measures on weighted hypergraphs
• Single backup table schemes for shortest-path routing [DOI] [Web of Scientce]
• Linear-time enumeration of isolated cliques [Web of Scientce]
• Three equivalent partial orders on graphs with real edge-weights drawn on a convex polygon [Web of Scientce]
• NA-edge-connectivity augmentation problems by adding edges [Web of Scientce]
• Subdivision of the hierarchy of H-colorable graph classes by circulant graphs [CiNii Research (CiNii Articles)]
• C_7-coloring problem [Web of Scientce]
• Imperfectness of data for STS-based physical mapping [DOI]
• Imperfectness of data for STS-based physical mapping [Web of Scientce]
• Avoiding routing loops on the Internet [DOI] [Web of Scientce]
• Source location problem with flow requirements in directed networks [DOI] [Web of Scientce]
• 加群上の畳込み符号による可変レートMPSK符号化変調方式 [DOI] [Web of Scientce]
• Sum of edge lengths of a multigraph drawn on a convex polygon [Web of Scientce]
• Polynomial time computable backup tables for shortest path routing [CiNii Research (CiNii Articles)]
• Can a hypergraph cover every convex polygon?
• Source location problems considering vertex-connectivity and edge-connectivity simultaneously [DOI] [Web of Scientce]
• On H-coloring problems with H expressed by complements of cycles, bipartite graphs, and chordal graphs [Web of Scientce]
• マルチホップ無線ネットワークにおける優先領域に基づく中継制御法 [CiNii Research (CiNii Articles)] [CiNii Books]
• 端末のパケット中継機能を用いた安否確認ネットワークの検討
• A Coloring Problem With Restrictions of Adjacent Colors [DOI]
• Channel assignment scheme for integrated voice and data traffic in reservation-type packet radio networks [Web of Scientce]
• File transfer tree problems [Web of Scientce]
• Avoiding routing loops on the Internet
• Comparing hypergraphs by areas of hyperedges drawn on a convex polygon [Web of Scientce]
• Minimum cost source location problem with vertex-connectivity requirements in digraphs [Web of Scientce]
• Lengths of tours and permutations on a vertex set of a convex polygon [Web of Scientce]
• A generalization of 2-dimension Ham Sandwich Theorem [Web of Scientce]
• Coloring problem with restrictions of adjacent colors expressed by cycles and bipartite graphs
• Source location problem with edge-connectivity requirements in digraphs [CiNii Research (CiNii Articles)]
• Location problems based on node-connectivity, and edge-connectivity between nodes and node-subsets [Web of Scientce]
• レイリーフェージング通信路に有効な環上の畳込み符号
• 手数制限付き一般化詰め将棋のPSPACE 完全性について [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Sum of edge lengths of a graph drawn on a convex polygon [Web of Scientce]
• A faster and flexible algorithm for a location problem on undirected flow networks [Web of Scientce]
• NP-completeness of reallocation problems with restricted block volume [Web of Scientce]
• NP-hardness of rotation type cell-mazes [Web of Scientce]
• Slot assignment scheme for integrated voice and data traffic in reservation-type packet radio networks [Web of Scientce]
• NP-completeness of stage illumination problems [Web of Scientce]
• 2-dimension ham sandwich theorem for partitioning into three convex pieces [Web of Scientce]
• The sum of chord lengths for convex polygons is a concave and increasing function
• Access control schemes for slotted ALOHA system with an adaptive array
• Linear time algorithms for graph search and connectivity determination on complement graphs [Web of Scientce]
• Sparse spanning subgraphs preserving connectivity and distance between vertices and vertex subsets [Web of Scientce]
• Edge connectivity between nodes and node-subsets [Web of Scientce]
• Repairing flaws in a picture based on a geometric representation of a digital image [Web of Scientce]
• A linear-time algorithm for determining the order of moving products in reallocation problems [Web of Scientce]
• Complexity and algorithm for reallocation problem [Web of Scientce]
• Computational complexity of multicommodity flow problems with uniform assignment of flow [Web of Scientce]
• CONNECTIVITY PROBLEMS ON AREA GRAPHS FOR LOCALLY STRIKING DISASTERS - DIRECT NA CONNECTION [Web of Scientce]
• フロー割当によるネットワーク性能推定法
• Network topology construction method and its support system [DOI]
• グラフにおける節点・領域連結度について [CiNii Research (CiNii Articles)]
• Hybrid control strategies for advanced network control and their intelligent decision support system [CiNii Research (CiNii Articles)]
• ダイナミックルーチングのための迂回候補群作成法 [CiNii Research (CiNii Articles)]
• 経由枝数に制限を持つ多品種流問題
• ADVANCED CALL-LEVEL ROUTING SCHEMES FOR HYBRID CONTROLLED DYNAMIC ROUTING [Web of Scientce]

その他業績

• ましゅの定数時間検査
• ネコ教授が楽しむ数学・計算機科学講義
• Unfolding and Dissection of Multiple Cubes, Tetrahedra, and Doubly Covered Squares [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• A Much Faster Algorithm for Finding a Maximum Clique with Computational Experiments [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Bumpy Pyramid Folding Problem (システム数理と応用) [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• Bumpy Pyramid Folding Problem [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• On A Generalization of River Crossing Problems [DOI]
• Testing graph rigidity in constant time
• ナップサック問題に対する定数時間近似アルゴリズム [CiNii Research (CiNii Articles)]
• An almost optimal algorithm for Winkler's sorting pairs in bins (コンピュテーシヨン) [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• STOC2009参加報告 [CiNii Research (CiNii Articles)]
• Constant-time approximations using minimum value search for independent sets and matchings
• DS-1-1 最大独立集合と最大マッチングに対する定数時間近似アルゴリズムの改善(DS-1. COMP学生シンポジウム,シンポジウムセッション) [CiNii Research (CiNii Articles)]
• Property testing on k-vertex-connectivity of graphs (コンピュテーション) [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• On k-connectivity testing in degree-bounded graphs
• 有向グラフにおけるk枝連結性の検査 [CiNii Research (CiNii Articles)]
• Efficient Methods for Determining DNA Probe Orders [CiNii Research (CiNii Articles)] [CiNii Books]
• グラフの変形操作における単純性の保存 [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link] [Othres link]
• ^^^--Coloring Problem [CiNii Research (CiNii Articles)] [CiNii Books]
• H-彩色可能なグラフのクラスの階層構造のCirculant graphs による細分化 [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link] [Othres link]
• 平面グラフのC7－彩色問題 [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link] [Othres link]
• グラフの平面凸描画の枝長と線形カットサイズと交差操作の関係 [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link] [Othres link]
• Variable Rate MPSK Coded Modulation Using Convolutional Codes over Modules [CiNii Research (CiNii Articles)] [CiNii Books]
• 優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討 [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• 優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討 [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• 優先領域に基づく中継制御法を用いたマルチホップ無線ネットワークの検討 [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• A Faster and Flexible Algorithm for a Location Problem on Undirected Flow Networks [CiNii Research (CiNii Articles)] [CiNii Books]
• 一般化詰め将棋問題の計算複雑さ : 小駒図式、成駒無し、還元玉、都詰の考慮 [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• 遠近問題を考慮した送信許可確率可変スロットアロハ方式の検討 [CiNii Research (CiNii Articles)] [CiNii Books]
• 遠近問題を考慮した送信許可確率可変スロットアロハ方式の検討 [CiNii Research (CiNii Articles)] [CiNii Books]
• 各節点の需要が異なる最小流入点集合配置問題 [CiNii Research (CiNii Articles)] [CiNii Books]
• （n-p）-点連結性のO（m+np3.5）時間判定法 [CiNii Research (CiNii Articles)] [CiNii Books] [Othres link]
• フロー割当てによるダイナミックルーチング網設計法 [CiNii Books] [CiNii Research]
• フロー割当によるネットワーク性能推定法の評価 [CiNii Research (CiNii Articles)] [CiNii Books]
• STR網におけるトラヒック流推定のためのフロー割当法の検討 [J-GLOBAL]
• ダイナミックルーチングSTRを考慮した回線算出法 [J-GLOBAL]
• 特集 ディジタル中継網におけるダイナミックルーチング方式の開発 ダイナミックルーチング(STR)の自律的迂回ルート選択機能とその性能評価 [J-GLOBAL]
• ルーチングにおけるハイブリッド制御の効果 [J-GLOBAL]
• 迂回候補群作成問題に関する発見的算法の効果 LPを用いた解法との比較 [J-GLOBAL]
• STRにおける迂回候補群作成法の予測誤り耐力の評価 [J-GLOBAL]
• 電話網における迂回候補群作成アルゴリズム [J-GLOBAL]
• 電話網における迂回候補群作成アルゴリズム [J-GLOBAL]

講演・口頭発表等

• Sublinear-Time Paradigm --- How to Challenge Big Data
• Generalized shogi and chess are constant-time tastable
• Transformation of Graphs and their Simpleness

書籍等出版物

• イラストで学ぶ離散数学
• データ構造とアルゴリズム（コンピュータサイエンス教科書シリーズ ２）
• ビッグデータ・マネジメント --- データサイエンティストのためのデータ利活用技術と事例 [Othres link]
• 離散数学のすすめ
• パズル・ゲームで楽しむ数学 --- 娯楽数学の世界
• 離散幾何学における未解決問題集
• アルゴリズム工学 --- 計算困難問題への挑戦
• ネットワーク設計理論（岩波講座「インターネット」第５巻）

作品等

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

• 劣線形時間パラダイムの展開
• 効率的な最大および極大クリーク抽出アルゴリズムの開発と応用
• 劣線形時間パラダイム
• 最大および極大クリーク抽出アルゴリズムの高効率化と応用
• 情報理論・符号理論からの計算限界研究
• データの巨大化から生じる不完全情報への対処に主眼をおいた近似計算
• ゲーム解析の新パラダイム
• ゲーム情報学：Ａｎｄ－Ｏｒ木の探索とゲーム・パズルの難しさの研究
• 空間的な情報補填を可能にするアルゴリズムの研究
• 巨大情報からの超高速情報抽出アルゴリズムの研究
• 情報補填を可能にするアルゴリズムの設計と解析
• 巨大情報のアルゴリズム的超圧縮技術の研究
• 新世代の計算限界-その解明と打破-
• ネットワーク問題のモデル化とアルゴリズムの研究
• 工学的評価基準に基づく離散アルゴリズムの品質保証技術に関する研究
• インターネット問題のモデル化法と効率的算法の研究
• グラフ・ネットワーク・離散幾何学におけるアルゴリズムの研究
• 工学的評価基準による離散アルゴリズムの高品質化に関する研究
• グラフ・ネットワーク構造を持つ離散最適化問題の定式化とその効率的解法の研究

メディア報道

産業財産権

所属学協会

• 日本オペレーションズ・リサーチ学会
• 電子情報通信学会
• 情報処理学会
• European Association for Theoretical Computer Science (EATCS)

委員歴

担当経験のある科目

社会貢献活動

学術貢献活動