UEHARA Ryuuhei

J-GLOBAL         Last updated: Nov 2, 2019 at 12:15
 
Avatar
Name
UEHARA Ryuuhei
Affiliation
Japan Advanced Institute of Science and Technology
Section
School of Information Science
Job title
Associate Professor
Degree
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-Communications (1998)

Research Areas

 
 

Academic & Professional Experience

 
 
   
 
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)
 

Education

 
 
 - 
1991
Graduate School, Division of Electro Communications, The University of Electro-Communications
 
 
 - 
1989
Faculty of Electro Communications, The University of Electro-Communications
 

Awards & Honors

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

Published Papers

 
Katsuhisa Yamanaka,Erik D. Demaine,Takashi Horiyama,Akitoshi Kawamura,Shin-Ichi Nakano,Yoshio Okamoto,Toshiki Saitoh,Akira Suzuki,Ryuhei Uehara,Takeaki Uno
J. Graph Algorithms Appl.   23(1) 3-27   Sep 2019   [Refereed]
Ryuhei Uehara
Bulletin of the EATCS   128(128) 109-112   Jun 2019   [Refereed]
上原 隆平
電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers   102(4) 297-299   Apr 2019
Koji Ouchi,Ryuhei Uehara
IEICE Transactions   102-D(3) 416-422   Mar 2019   [Refereed]
Ryuhei Uehara
1-175   2019   [Refereed]

Misc

 
Tree Spanners for Bipartite Graphs and Probe Interval Graphs(jointly authored)
Lecture Notes in Computer Science   (2880) 106-118   2003
Tighter Bounds on the Genus of Nonorthogonal Polyhedra Built from Rectangles(jointly authored)
Canadian Conference on Computational Geometry   105-108   2002
Completeness of Graph Isomorphism Problem for Bipartite Graph Classes(jointly authored)
IEICE Technical Report   COMP2001(93) 1-5   2002
Fast Parallel Approximation Algorithms for Maximum Weight Matching Problem
IDSJ SIG Notes   2000-AL-71(33-40)    2000
Tractable Problems on Small Connected Components in Graphs
KOREA-JAPAN Joint Workshop on Algorithms and Computation   116-122   1999

Books etc

 
First Course in Algorithms Through Puzzles
Ryuhei Uehara
Springer   2018   
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   
Games, Puzzles, and Computation
Robert Hearn and Erik D. Demaine (Part:Single Translation)
2011   
Geometric Folding Algorithms
Erik D. Demaine, Joseph O'Rourke (Part:Single Translation)
2009   ISBN:978-4-7649-0377-7
Site Consistency in Phylogenetic Networks with Recombination, in Algorithmics in Bioniformatics
Tetsuo Asano, Patricia Evans, Ryuhei Uehara, and Gabriel Valiente
College Publications   2006   

Conference Activities & Talks

 
Counting the Independent Sets of a Chordal Graph
Yoshio Okamoto, Takeaki Uno, and Ryuhei Uehara
IPSJ SIG Technical Report, 2004-AL-96, pp.17-24   27 Jul 2004   
Longest Paths in Small Graph Classes
Ryuhei Uehara and Yushi Uno
IEICE Technical Report, COMP2004-16, pp.53-60   20 May 2004   
Extended MPQ-trees for Probe Interval Graphs
Ryuhei Uehara
IPSJ SIG Technical Report, 2004-AL-93, pp.97-104   30 Jan 2004   
Canonical MPQ-tree Model for Interval Graphs
Ryuhei Uehara
Forum on Information Technology (FIT2003), A-037, pp.79-81   11 Sep 2003   
Tree Spanners for Bipartite Graphs and Probe Interval Graphs
Andreas Brandstädt, Feodor F. Dragan, Hoang-Oanh Le, Van Bang Le, and Ryuhei Uehara
IPSJ SIG Technical Report, 2003-AL-90,pp.57-64   23 May 2003   
Completeness of Graph Isomorphism Problem for Bipartite Graph Classes
Takayuki Nagoya, Ryuhei Uehara, and Seinosuke Toda
IEICE Technical Report, COMP2001-93,pp.1-5   12 Mar 2002   
Expected Length of Longest Common Subsequences of Two Biased Random Strings and Its Application
Hironobu Aoki, Ryuhei Uehara and Koichi Yamazaki
LA Symposium   17 Jul 2000   
Fast Parallel Approximation Algorithms for Maximum Weight Matching Problem
Ryuhei Uehara
IPSJ SIG Notes,2000-AL-71,pp.33-40   7 Nov 2000   
The Number of Connected Components in Graphs and Its Applications
Ryuhei Uehara
IEICE Technical Report,COMP99-10,pp.1-8   24 May 1999   
Tractable and Intractable Problems on Generalized Chordal Graphs
Ryuhei Uehara
IEICE Technical Report,COMP98-83,pp.1-8   24 Mar 1999   
Unique Solution Instance Generation for the 3-Satisfiability (3SAT) Problem
Mitsuo Motoki and Ryuhei Uehara
IEICE Technical Report,COMP98-54,pp.25-32   20 Nov 1998   
Parallel Complexity of the Lexicographically First Maximal Subgraph Problems on Restricted Graphs
Ryuhei Uehara
IEICE Technical Report,COMP97-68,pp.65-72   14 Nov 1997   
A Measure of Parallelization for the Lexicographically First Maximal Independent Set Problem
Ryuhei Uehara
IPSJ SIG Notes,97-AL-56,pp.19-26   14 Mar 1997   
Partial Gates and Their Identifications
Ryuhei Uehara, and Kensei Tsuchida
IEICE Technical Report,COMP96-22,pp.1-10   25 Jul 1996   
RNC and NC Algorithms for Maximal Path Sets and Applications to Superstrings with Flipping
Ryuhei Uehara, Zhi-Zhong Chen, and Xin He
1 Feb 1996   
Complexity Classes Characterized by Many Computation Paths
Ryuhei Uehara
IEICE Technical Report,COMP95-42,pp.9-15   22 Sep 1995   
Complexity Classes Characterized by Semi-Random Sources
Ryuhei Uehara
14 Jun 1995   
Efficient Simulations by a Biased Coin
Ryuhei Uehara
18 Jul 1994   
Laminar Structure of Ptolemaic Graphs and Its Applications
Ryuhei Uehara and Yushi Uno
IEICE Technical Report, COMP2005-30   15 Sep 2005   
Voronoi Game on Graphs and Its Complexity
Sachio Teramoto and Ryuhei Uehara
IPSJ SIG Technical Report, 2006-AL-104-2, pp.9-16   20 Jan 2006   
Canonical Tree Representation of Distance Hereditary Graphs and Its Applications
Ryuhei Uehara and Takeaki Uno
IEICE Technical Report, COMP2005-61, pp.31-38   22 Mar 2006   
Heuristics for Generating a Simple Polygonalization
Sachio Teramoto, Mitsuo Motoki, Ryuhei Uehara, Tetsuo Asano
IPSJ SIG Technical Report, 2006-AL-106-6, pp.41-48   18 May 2006   
The complexity of a Pop-up book
Ryuhei Uehara and Sachio Teramoto
IPSJ SIG Technical Report, 2006-AL-107-10, pp.59-64   3 Jul 2006   
Efficient Algorithms for Airline Problem
Ryuhei Uehara
IEICE Technical Report, COMP2006-34, pp.25-31   17 Oct 2006   
Do Interval Graphs Dream of Scale-free Network?
Takeya Shigezumi, Ryuhei Uehara and Osamu Watanabe
18 Jul 2007   
Bandwidth of Bipartite Permutation Graphs
Ryuhei Uehara
IEICE Technical Report, COMP 2007-36, pp.29-34   20 Sep 2007   
Polygons Folding to Plural Incongruent Orthogonal Boxes
Jun Mitani, Ryuhei Uehara
IEICE Technical Report, COMP2008-23, pp. 1-8   11 Sep 2008   
Polygons Folding to Plural Incongruent Orthogonal Boxes
Jun Mitani, Ryuhei Uehara
Acceleration and Visualization of Computation for Enumeration Problems, pp. 135-149   29 Sep 2008   
On the Complexity of Reconfiguration Problems
Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno
IEICE Technical Report, COMP2008-36, pp. 17-24   10 Oct 2008   
Efficient Enumeration of All Ladder Lotteries
Katsuhisa Yamanaka, Shin-ichi Nakano, Yasuko Matsui, Ryuhei Uehara, and Kento Nakada
Workshop on Topological Graph Theory   24 Nov 2008   
Complexity of Pleats Folding
Tsuyoshi Ito, Masashi Kiyomi, Shinji Imahori, and Ryuhei Uehara
IPSJ SIG Technical Report, 2008-AL-122-1, pp. 1-8   30 Jan 2009   
Efficient Enumeration of All Ladder Lotteries
Katsuhisa Yamanaka, Shin-ichi Nakano, Yasuko Matsui, Ryuhei Uehara, and Kento Nakada
IEICE Technical Report, COMP2008-56, pp. 17-23   2 Mar 2009   
Efficient Enumeration of All Pseudoline Arrangements
Katsuhisa Yamanaka, Shin-ichi Nakano, Yasuko Matsui, Ryuhei Uehara, and Kento Nakada
IPSJ SIG Technical Report, 2009-AL-124, pp. 1:1-1:6   11 May 2009   
On Scale free k-trees
Colin Cooper and Ryuhei Uehara
IPSJ SIG Technical Report, 2009-AL-124, pp. 2:1-2:8   11 May 2009   
Counting the Number of Matching in Chordal and Chordal Bipartite Graph Classes
Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno
IEICE Technical Report, COMP2009-??   29 Jun 2009   
Graph Orientation Problems for Multiple st-Reachability
Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki, Ryuhei Uehara
IPSJ SIG Technical Report, 2009-AL-125, pp. 5:1-5:?   21 Jul 2009   
Enumeration of Perfect Sequences of Chordal Graph
Yasuko Matsui, Ryuhei Uehara, Takeaki Uno
Acceleration and Visualization of Computation for Enumeration Problems   29 Sep 2008   
Reconstruction of Connected Interval Graphs
Masashi Kiyomi, Toshiki Saitoh, Ryuhei Uehara
Acceleration and Visualization of Computation for Enumeration Problems   29 Sep 2008   
Random Generation and Enumeration of Bipartite Permutation Graphs
Toshiki Saitoh, Yota Otachi, Katuhisa Yamanaka, and Ryuhei Uehara
IEICE Technical Report, COMP2009-??, pp. ??-??   14 Sep 2009   
Voronoi Game on a Path
Toshiki Saito, Masashi Kiyomi, and Ryuhei Uehara
IEICE Technical Report, COMP2010-10, pp. 1-5   19 May 2010   
Stretch Minimization Problem of a Strip Paper
Ryuhei Uehara
IPSJ SIG Technical Report, 2010-AL-130-2, pp. 7-13   19 May 2009   
NP-completeness of generalized Kaboozle
Tetsuo Asano, Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara
IPSJ SIG Technical Report, 2010-AL-130-3, pp. 15-20   19 May 2009   
Undecidability of Origami
Ryuhei Uehara
IPSJ SIG Tecninical Report, 2010-AL-131-11, pp. 1-3   22 Sep 2010   
Bipartite powers of interval bigraphs
Yoshio Okamoto, Yota Otachi, and Ryuhei Uehara
IEICE Technical Report, COMP 2010-36, VOl. 110, No. 232, pp. 35-39   15 Oct 2010   
Nonexistence of Common Edge Developments of Regular Tetrahedron and Other Platonic Solids
Takashi Horiyama and Ryuhei Uehara
IPSJ SIG Technical report, 2010-AL-132-1, pp. 1-4   19 Nov 2010   
Construction of Common Unfolding of a Regular Tetrahedron and a Cube
Toshihiro Shirakawa, Takashi Horiyama, and Ryuhei Uehara
IPSJ SIG Technical Report, 2010-AL-135-10, pp.1-5   16 May 2011   
Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, and Takeaki Uno
IPSJ SIG Technical Report, 2011-AL-136-5, pp. 1-8   6 Sep 2011   
The graph isomorphism problem on graphs with geometric represenations
Ryuhei Uehara
4th Biennial Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM)   10 Jun 2013   
On generation of graphs with geometric representations
Ryuhei Uehara
4th Biennial Canadian Discrete and Algorithmic Mathematics Conference (CanaDAM)   10 Jun 2013   
The Graph Isomorphism Problem on Geometric graphs, [Invited]
Ryuhei Uehara
The 2nd Pacific Rim Mathematical Association (PRIMA)   24 Jun 2013   
Zipper Unfolding of Simple Convex Polyhedra
Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara
IPSJ SIG Technical Report, 2013-AL-146-4, pp. 1-6   30 Jan 2014   
Algorithms for independent set reconfiguration problem on graphs
Erik D. Demaine, Martin L. Demaine, Takehiro Ito, Hirotaka Ono, and Ryuhei Uehara
IEICE Technical Report, COMP2013-39, Vol. 113, No. 371, pp. 7-14   20 Dec 2013   
Bumpy Pyramid Folding Problem
Zachary Abel, Erik D. Demaine, Martin L. Demaine, Hiro Ito, Jack Snoeyink, and Ryuhei Uehara
IPSJ SIG Technical Report, 2013-AL-145-9, pp. 1-7   6 Nov 2013   
Computational Complexity of Piano-Hinged Dissections
Zachary Abel, Erik D. Demaine, Martin L. Demaine, Takashi Horiyama, and Ryuhei Uehara
IPSJ SIG Technical Report, 2013-AL-144-6, pp. 1-6   17 May 2013   
On Computational Complexity and an Integer Programming model of Shakashaka
Erik D. Demaine, Yoshio Okamoto, Ryuhei Uehara, and Yushi Uno
IEICE Technical Report, COMP2013-8, Vol. 113, No. 14, pp. 43-48   24 Apr 2012   
On the Complexity of Packing Trominoes
Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, Ryuhei Uehara
IEICE Technical Report, COMP2012-40, Vol. 112, No. 272, pp. 37-43   31 Oct 2012   
Approximation for the Geometric Unique Coverage Problem on Unit Squares
Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno
IEICE Technical Report, COMP2012-24, Vol. 112, No. 93, pp. 95-101   21 Jun 2012   
On the Base-Line Location Problem for the Maximum Weight Region Decomposable into Base-Monotone Shapes
Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno
IEICE Technical Report, COMP2012-6, Vol. 112, No. 21, pp. 37-43   27 Apr 2012   
On the number of reduced tree, cographs, and series-parallel graphs by compression
Takeaki Uno, Ryuhei Uehara, and Shin-ichi Nakano
IPSJ SIG Technical Report, 2011-AL-137-6, pp. 1-8   18 Nov 2011   
Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs
Matsuo Konagaya, Yota Otachi, and Ryuhei Uehara
IPSJ SIG Technical Report, 2013-AL-147-12, pp. 1-6   3 Mar 2014   
The Convex Configurations of Dissection Puzzles with Seven Pieces.
Kazuho Katsumata and Ryuhei Uehara
IPSJ SIG Technical Report, 2015-AL-152-9, pp. 1-4   3 Mar 2015   
Ls in L and Sphinxes in Sphinx
Takashi Horiyama, Yoshio Okamoto, and Ryuhei Uehara
IPSJ SIG Technical Report, 2015-AL-154-9, pp. 1-3   28 Sep 2015   
Computational Complexity of Competitive Diffusion on (Un)weighted Graphs.
Takehiro Ito, Yota Otachi, Toshiki Saitoh, Hisayuki Satoh, Akira Suzuki, Kei Uchizawa, Ryuhei Uehara, Katsuhisa Yamanaka, and Xiao Zhou:
IPSJ SIG Technical Report, 2015-AL-154-8, pp. 1-6   28 Sep 2015   
Space Efficient Greedy Algorithms on Intervals.
Toshiki Saitoh, Takashi Horiyama, David Kirkpatrick, Yota Otachi, Ryuhei Uehara, and Yushi Uno
IPSJ SIG Technical Report, 2015-AL-154-4, pp. 1-7   28 Sep 2015   
Shortest Reconfiguration of Sliding Tokens on a Caterpillar.
Takeshi Yamada and Ryuhei Uehara
IPSJ SIG Technical Report, 2015-AL-155-1, pp. 1-8   20 Nov 2015   
Sliding token on unicyclick graphs.
Duc A. Hoang and Ryuhei Uehara
IPSJ SIG Technical Report, 2015-AL-157-5, pp. 1-7   6 Mar 2016   
Computational Complexity of Sequential Token Swapping Problem
Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, and Takeaki Uno
IEICE Technical Report, COMP2016-13, Vol. 116, No. 116, pp. 115-121   24 Jun 2016   
Counting the Number of Solutions for Peg Solitaire
Itsuki Kanemoto, Toshiki Saitoh, Masashi Kiyomi, and Ryuhei Uehara
IEICE Technical Report, COMP2016-14, Vol. 116, No. 211, pp. 1-5   6 Sep 2016   
Experimental Enumeration of Solutions for Peg Solitaire
Taishi Oikawa, Itsuki Kanemoto, Toshiki Saitoh, Masashi Kiyomi, and Ryuhei Uehara
IPSJ SIG Technical Report, 2016-AL-159-3, p. 1   23 Sep 2016   
Development of Peg Solitaire Font
Taishi Oikawa, Kazuaki Yamazaki, Tomoko Taniguchi, Ryuhei Uehara
IEICE Technical Report, COMP2016-50, Vol. 116 No. 503, pp. 1-4   7 Mar 2017   
Folding and unfolding algorithms on (super)computer [Invited]
Ryuhei Uehara
The 5th International Symposium on Computing and Networking (CANDAR 2017)   19 Nov 2017   

Research Grants & Projects

 
Study of Efficient Algorithms
Grant-in-Aid for Scientific Research

Social Contribution

 
The 13th Japan-Korea Joint Workshop on Algorithms and Computation
[]  JAIST, Professor, Tetsuo AsanoJAIST, Associate Professor, Ryuhei Uehara  (Kanazawa Culture Hall, Kanazawa, Ishikawa, Japan)  23 Jul 2010 - 24 Jul 2010
Japan Conference on Computational Geometry and Graphs
[]  JAIST, Professor, Tetsuo AsanoKyoto University, Associate Professor, Hiro ItoJAIST, Associate Professor, Ryuhei Uehara  (Kanazawa Culture Hall)  11 Nov 2009 - 13 Nov 2009
Workshop on Algorithms and Computation
[]  Indian Statistical Institute, Professor, Sandip Das,JAIST, Associate Professor, Ryuhei Uehara  18 Feb 2009 - 20 Feb 2009