TOP Page >  Faculty List by Area >  Profile

情報研究棟IS Building I 6F
To Lab's Site


Full text / JAIST Repository



Ryuuhei Uehara Professor
School of Information Science、Entertainment Technology Area


Master's thesis, Dep. Computer Science and Information Mathematics, University of Electro-Communications (1991)Ph.D thesis, Dp. Computer Science and Information Mathematics, University of Electro-Comm

■Professional Career

Canon Inc., Information Science Research Center (1991)Assistant, Tokyo Woman's Christian University (1993)Lecturer, Komazawa University (1998)Part time lecturer, Tokyo Institute of Technology (1998)Part time lecturer, Hitotsubashi University (1999)Researcher, University of Waterloo (2001)Associate Professor, Komazawa University (2001)


Computational Complexity and Graph Algorithms

■Research Keywords

Computational complexity, Graph theory, Algorithms

■Research Interests

Design and analysis of efficient algorithms for hard problems on restricted graph classes
There are many hard problems on general graphs from the viewpoint of computational complexity. However, some problems can be solved efficiently if the input graphs are restricted. My research topic is to design/analysis of the efficient algorithms, especially, for subclasses of perfect graphs.
Study on rigid graph structure like Origami
Origami can be seen as a rigid graph structure that consists of faces, crease lines, and points. From the viewpoint of theoretical computer science, I study the efficiency and complexity of geometric foldings for such rigid graph structure.



  • The Best Writing on Mathematics 2018, Tangled Tangles,Erik D. Demaine, Martin L. Demaine, Adam Hesterberg, Quanquan Liu, and Ryuhei Uehara,Princeton University Press,2018,83-96
  • First Course in Algorithms Through Puzzles,Ryuhei Uehara,Springer,2018,1-175
  • ORIGAMI6,Koryo Miura, Toshikazu Kawasaki, Tomohiro Tachi, Ryuhei Uehara, Robert J. Lang, and Patsy Wang-Inverson (Editors),American Mathematical Society, 2015.

Display All

◇Published Papers

  • Voronoi Game on a Path,Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara,IEICE TRANS. INF. & SYST., 2011,Vol. E94-D,pp. 1185-1189
  • A Double Classification Tree Search Algorithm for Index SNP Selection,Peisen Zhang, Huitao Sheng, and Ryuhei Uehara,BMC Bioinformatics(,5,89
  • Parallel Approximation Algorithms for Maximum Weighted Matching in General Graphs,Ryuhei Uehara and Zhi-Zhong Chen,Information Processing Letters,76,13-17

Display All

◇Lectures and Presentations

  • Folding and unfolding algorithms on (super)computer,Ryuhei Uehara,The 5th International Symposium on Computing and Networking (CANDAR 2017), Aomori, Japan, November 19-22, 2017.
  • On generation of graphs with geometric representations,Ryuhei Uehara,4th Biennial Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM),Canada,2013/06/10-2013/06/13
  • The graph isomorphism problem on graphs with geometric represenations,Ryuhei Uehara, 4th Biennial Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM),Canada,2013/06/10-2013/06/13

Display All

■Extramural Activities

◇Academic Society Affiliations

  • The Institute of Electronics, Information and Communication Engineers,2003-
  • EATCS,2001-
  • Association for Computing Machinery,1997-

Display All

◇Other Activities

  • Information Processing Letters,Editor
  • Journal of Information Science and Engineering,Editor
  • SIGAL,Manager,2010/04/01 - 2012/03/31

Display All

■Academic Awards Received

  • IPSJ Yamashita SIG Research Award,Information Processing Society of Japan,2012
  • EATCS/LA Best Presentation Award,EATCS Japan Chapter and LA Symposium,2009