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
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
Computational complexity, Graph theory, Algorithms
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，2019，1-175
- A Survey and Recent Results about Common Developments of Two or More Boxes in Origami6，Ryuhei Uehara，pp. 77-84, American Mathematical Society, 2015.
- 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(http://www.biomedcentral.com/bmcbioinformatics/)，5，89
- Parallel Approximation Algorithms for Maximum Weighted Matching in General Graphs，Ryuhei Uehara and Zhi-Zhong Chen，Information Processing Letters，76，13-17
◇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.
- 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
- 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
◇Academic Society Affiliations
- The Institute of Electronics, Information and Communication Engineers，2003-
- Association for Computing Machinery，1997-
- Information Processing Letters，Editor
- Journal of Information Science and Engineering，Editor
- SIGAL，Manager，2010/04/01 - 2012/03/31
■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