Technical Reports and other talks by R. Uehara

Note: The reports entitled in English are written in English, while the reports entitled in Japanese are written in Japanese.
  1. Zachary Abel, Erik Demaine, Martin Demaine, Hiroaki Matsui, Guenter Rote and Ryuhei Uehara: Common Developments of Several Different Orthogonal Boxes, IPSJ SIG Technical Report, 2011-AL-136-11, pp. 1-7, 2011/9/6.
  2. Hiroyuki Fukui, Akihiro Nakanishi, Ryuhei Uehara, Takeaki Uno, and Yushi Uno: The Complexity of Free Flood Filling Games, IPSJ SIG Technical Report, 2011-AL-136-7, pp. 1-5, 2011/9/6.
  3. Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, and Takeaki Uno: Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem, IPSJ SIG Technical Report, 2011-AL-136-5, pp. 1-8, 2011/9/6.
  4. Toshihiro Shirakawa, Takashi Horiyama, and Ryuhei Uehara: Construction of Common Unfolding of a Regular Tetrahedron and a Cube, IPSJ SIG Technical Report, 2010-AL-135-10, pp. 1-5, 2011/5/16.
  5. Takuya Umesato, Toshiki Saitoh, Ryuhei Uehara, and Hiro Ito: Complexity of the stamp folding problem, IPSJ SIG Technical Report, 2010-AL-135-9, pp. 1-7, 2011/5/16.
  6. 岡山陽介，清見礼，上原隆平: 複数の単位円による点集合の排他的被覆， IPSJ SIG Technical Report, 2010-AL-134-19, pp. 1-8, 2011/3/7.
  7. Arata Goto and Ryuhei Uehara: On the Hoffman Puzzle and its generalization, IPSJ SIG Technical Report, 2010-AL-134-18, pp. 1-4, 2011/3/7.
  8. Takashi Horiyama and Ryuhei Uehara: Nonexistence of Common Edge Developments of Regular Tetrahedron and Other Platonic Solids, IPSJ SIG Technical Report, 2010-AL-132-1, pp. 1-4, 2010/11/19.
  9. Yoshio Okamoto, Yota Otachi, and Ryuhei Uehara: Bipartite powers of interval bigraphs, IEICE Technical Report, COMP2010-36, Vol. 110, No. 232, pp. 35-39, 2010/10/15.
  10. Ryuhei Uehara: Undecidability of Origami, IPSJ SIG Technical Report, 2010-AL-131-11, pp. 1-3, 2010/09/22.
  11. 上原隆平： 折りたたみに関する計算量， 日本応用数理学会2010年度年会： 折紙工学(1)， 日本応用数理学会，2010/09/08．
  12. 上原隆平： 折紙のアルゴリズム， 夏期セミナー， 情報オリンピック日本委員会， 2010/08/26． （当日の模様）
  13. 上原隆平： じゃばら折りの一般化とその複雑さの研究， ERATOセミナー， ERATO湊離散構造処理系プロジェクト， 2010/08/04．
  14. Tetsuo Asano, Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara: NP-completeness of generalized Kaboozle, IPSJ SIG Technical Report, 2010-AL-130-3, pp. 15-20, 2010/5/19.
  15. Ryuhei Uehara: Stretch Minimization Problem of a Strip Paper, IPSJ SIG Technical Report, 2010-AL-130-2, pp. 7-13, 2010/5/19.
  16. Toshiki Saito, Masashi Kiyomi, and Ryuhei Uehara: Voronoi Game on a Path, IEICE Technical Report, COMP2010-10, pp. 1-5, 2010/5/19.
  17. 清見礼，齊藤寿樹，上原隆平: パス上のボロノイゲーム， 組合せゲーム・パズル ミニプロジェクト, 2010/3/1.
  18. Tetsuo Asano, Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara: Kaboozle is NP-complete even in a strip form, 組合せゲーム・パズル ミニプロジェクト, 2010/3/1.
  19. 栗林康之，齊藤寿樹，上原隆平： 二部区間グラフの効率のよい認識アルゴリズムに関する研究 計算機科学の理論とその応用(冬のLAシンポジウム)， pp.27:1-6, 2009/2/2.
  20. Toshiki Saito, Masashi Kiyomi, and Ryuhei Uehara: Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs, IPSJ SIG Technical Report, 2009-AL-126, pp. 5:1-5:?, 2009/9/15.
  21. Toshiki Saitoh, Yota Otachi, Katuhisa Yamanaka, and Ryuhei Uehara: Random Generation and Enumeration of Bipartite Permutation Graphs, IEICE Technical Report, COMP2009-??, pp. ??-??, 2009/9/14.
  22. Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki, Ryuhei Uehara: Graph Orientation Problems for Multiple st-Reachability, IPSJ SIG Technical Report, 2009-AL-125, pp. 5:1-5:?, 2009/7/21.
  23. Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno: Counting the Number of Matching in Chordal and Chordal Bipartite Graph Classes, IEICE Technical Report, COMP2009-24, pp. 45-52, 2009/6/29.
  24. Colin Cooper, Ryuhei Uehara: On Scale free k-trees, IPSJ SIG Technical Report, 2009-AL-124, pp. 2:1-2:8, 2009/5/11.
  25. Katsuhisa Yamanaka, Shin-ichi Nakano, Yasuko Matsui, Ryuhei Uehara, and Kento Nakada: Efficient Enumeration of All Pseudoline Arrangements, IPSJ SIG Technical Report, 2009-AL-124, pp. 1:1-1:6, 2009/5/11.
  26. 伊藤 健洋, 上原 隆平, 小野 廣隆, 玉木 久夫, 宮本 裕一郎: なるべく遠回りしなくてすむように一方通行を決める問題の難しさ, 日本応用数理学会 離散システム研究部会, 2009/3/8.
  27. Katsuhisa Yamanaka, Shin-ichi Nakano, Yasuko Matsui, Ryuhei Uehara, and Kento Nakada: Efficient Enumeration of All Ladder Lotteries, IEICE Technical Report, COMP2008-56, pp. 17-23, 2009/3/2.
  28. 岡本吉央, 上原隆平: 絵画的迷路の作り方, 計算機科学の理論とその応用(冬のLAシンポジウム)，pp.10:1-8, 2009/2/2.
  29. Tsuyoshi Ito, Masashi Kiyomi, Shinji Imahori, and Ryuhei Uehara: Complexity of Pleats Folding, IPSJ SIG Technical Report, 2008-AL-122-1, pp. 1-8, 2009/1/30.
  30. Naoto Miyoshi, Mariko Ogura, Takeya Shigezumi, and Ryuhei Uehara: Subexponential interval graphs generated by immigration-death processes, Dept. of Math. and Comp. Sciences Research Report, B-451, 2008/12.
  31. Katsuhisa Yamanaka, Shin-ichi Nakano, Yasuko Matsui, Ryuhei Uehara, and Kento Nakada: Efficient Enumeration of All Ladder Lotteries, The 20th Workshop on Topological Graph Theory, 2008/11/24-28.
  32. Takehiro Ito, Erik D. Demaine, Nicholas J. A. Harvey, Christos H. Papadimitriou, Martha Sideri, Ryuhei Uehara, and Yushi Uno: On the Complexity of Reconfiguration Problems, IEICE Technical Report, COMP2008-36, pp. 17-24, 2008/10/10.
  33. 上原隆平: 折り紙の計算論的複雑さの研究, 社団法人日本機械学会産官学連携センター研究協力事業委員会所属 「RC235　計算力学援用による折紙工学の推進とその応用に関する調査研究分科会」 招待講演, 2008/10/7. (当日使ったPowerPointのファイル)
  34. Jun Mitani, Ryuhei Uehara: Polygons Folding to Plural Incongruent Orthogonal Boxes, Acceleration and Visualization of Computation for Enumeration Problems, pp. 135-149, 2008/9/29-30.
  35. Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara: Reconstruction of Connected Interval Graphs, Acceleration and Visualization of Computation for Enumeration Problems, pp. 128-134, 2008/9/29-30.
  36. Yasuko Matsui, Ryuhei Uehara, and Takeaki Uno: Enumeration of Perfect Sequences of Chordal Graph, Acceleration and Visualization of Computation for Enumeration Problems, pp. 86-94, 2008/9/29-30.
  37. Jun Mitani, Ryuhei Uehara: Polygons Folding to Plural Incongruent Orthogonal Boxes, IEICE Technical Report, COMP2008-23, pp. 1-8, 2008/9/11. (Support pages are written in English and Japanese.)
  38. 上原 隆平, 河村泰之, 松永博充, 元木光雄: ある投票ゲームのシミュレーション, IEICE Technical Report, COMP2008-20, pp.37-42, 2008/6/16.
  39. Yasuko Matsui, Ryuhei Uehara, Takeaki Uno: Enumeration of Perfect Sequences of Chordal graph, IEICE Technical Report, COMP2008-3, pp.15-21, 2008/4/18.
  40. Takeya Shigezumi, Naoto Miyoshi, Ryuhei Uehara, Owamu Watanabe: Scale Free Interval Graphs, COMP-NHC学生シンポジウム, DS-1-7, 2008/3/18.
  41. Ryuhei Uehara: Bandwidth of Bipartite Permutation Graphs, IEICE Technical Report, COMP2007-36, pp.29-34, 2007/9/20.
  42. 上原隆平，河村泰之，松永博充，元木光雄: ある投票ゲームに関する戦略のモデル化, 計算機科学の理論とその応用(夏のLAシンポジウム)， pp.4:1-4:3, 2007/7/18.
  43. Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe: Do Interval Graphs Dream of Scale-free Network?, 計算機科学の理論とその応用(夏のLAシンポジウム)， pp.3:1-3:3, 2007/7/18.
  44. Toshiki Saitoh, Masashi Kiyomi, Ryuhei Uehara: Simple Efficient Algorithm for MPQ-tree of an Interval Graph, IEICE Technical Report, COMP2007-24, pp.49-54, 2007/6/29.
  45. 高原祥浩，寺本幸生，上原隆平: Ptolemaic Graph 上の最長路問題に関する研究， 計算機科学の理論とその応用(冬のLAシンポジウム)， pp.18:1-18:10, 2007/1/29.
  46. 斎藤寿樹，清見礼，上原隆平: 区間表現からMPQ-treeを構築するアルゴリズム， 計算機科学の理論とその応用(冬のLAシンポジウム)， pp.16:1-16:10, 2007/1/29.
  47. Shin-ichi Nakano, Ryuhei Uehara, Takeaki Uno: Efficient Algorithms for Airline Problem, 新世代の計算限界 −その解明と打破− ミニシンポジウム： 新世代計算限界と地球環境問題， pp.51-60, 2006/12/6. (Here is the current version in English.)
  48. Ryuhei Uehara: Efficient Algorithms for Airline Problem, IEICE Technical Report, COMP2006-34, pp.25-31, 2006/10/17. (The results are updated; see above.)
  49. 上原隆平: グラフクラスとアルゴリズム, IEICE Technical Report, Lecture talk, 2006/9/26. (The PDF file (520263bytes) of the talk is available, but in Japanese.)
  50. Ryuhei Uehara and Sachio Teramoto: The complexity of a Pop-up book, IPSJ SIG Technical Report, 2006-AL-107-10, pp.59-64, 2006/7/3. PDF file (126431 bytes)
  51. 平山亮，上原隆平: スケールフリーグラフ上における局所情報を用いたランダムウォークについて, IPSJ SIG Technical Report, 2006-AL-107-6, pp.31-37, 2006/7/3.
  52. Sachio Teramoto, Mitsuo Motoki, Ryuhei Uehara, and Tetsuo Asano: Heuristics for Generating a Simple Polygonalization, IPSJ SIG Technical Report, 2006-AL-106-6, pp.41-48, 2006/5/18.
  53. Ryuhei Uehara and Takeaki Uno: Canonical Tree Representation of Distance Hereditary Graphs and Its Applications, IEICE Technical Report, COMP2005-61, pp.31-38, 2006/3/22. PDF file (183992 bytes)
  54. Sachio Teramoto and Ryuhei Uehara: Voronoi game on graphs and its complexity, IPSJ SIG Technical Report, 2006-AL-104-2, pp.9-16, 2006/1/20. See the conference version with Erik D. Demaine.
  55. Ryuhei Uehara and Yushi Uno: Laminar Structure of Ptolemaic Graphs and Its Applications, IEICE Technical Report, COMP2005-30, pp.17-24, 2005/9/15. PDF file (281249 bytes)
  56. Ryuhei Uehara and Yushi Uno: On the Laminar Structure of Ptolemaic and Distance Hereditary Graphs, Complexity Seminar(Informal seminar in Japanese), 2005/3/19. PDF file (109327 bytes).
  57. Ryuhei Uehara: Efficient Algorithms for the Longest Path Problem, Workshop on New Horizons in Computing (NHC), 2005/3/1. PDF file (231075 bytes).
  58. Yoshio Okamoto, Takeaki Uno, and Ryuhei Uehara: Counting the Independent Sets of a Chordal Graph, IPSJ SIG Technical Report, 2004-AL-96, pp.17-24, 2004/7/27. PDF file(217092 bytes).
  59. Ryuhei Uehara and Yushi Uno: Longest Paths in Small Graph Classes, IEICE Technical Report, COMP2004-16, pp.53-60, 2004/5/20. PDF file(231075 bytes).
  60. Ryuhei Uehara: Extended MPQ-trees for Probe Interval Graphs, IPSJ SIG Technical Report, 2004-AL-93, pp.97-104, 2004/1/30. PDF file(284234 bytes), ps file(133396 bytes, compressed by gzip).
  61. Ryuhei Uehara: Canonical MPQ-tree Model for Interval Graphs, Forum on Information Technology (FIT2003), A-037, pp.79-81, 2003/9/11.
  62. Andreas Brandstädt, Feodor F. Dragan, Hoang-Oanh Le, Van Bang Le, and Ryuhei Uehara: Tree Spanners for Bipartite Graphs and Probe Interval Graphs, IPSJ SIG Technical Report, 2003-AL-90, pp.57-64, 2003/5/23. PDF file(314069 bytes).
  63. Takayuki Nagoya, Ryuhei Uehara, and Seinosuke Toda: Completeness of Graph Isomorphism Problem for Bipartite Graph Classes, IEICE Technical Report, COMP2001-93, pp.1-5, 2002/3/12. PostScript file (40232 bytes, compressed by gzip).
  64. Hironobu Aoki, Ryuhei Uehara and Koichi Yamazaki: Expected Length of Longest Common Subsequences of Two Biased Random Strings and Its Application, LA Symposium, 2000/7/17.
  65. Ryuhei Uehara: Fast Parallel Approximation Algorithms for Maximum Weight Matching Problem, IPSJ SIG Notes, 2000-AL-71, pp.33-40, 2000/1/17. PostScript file (57711 bytes, compressed by gzip).
  66. Ryuhei Uehara: The Number of Connected Components in Graphs and Its Applications, IEICE Technical Report, COMP99-10, pp.1-8, 1999/5/24. PostScript file (51038 bytes, compressed by gzip).
  67. Ryuhei Uehara: Tractable and Intractable Problems on Generalized Chordal Graphs, IEICE Technical Report, COMP98-83, pp.1-8, 1999/3/24. PostScript file (58356 bytes, compressed by gzip).
  68. Mitsuo Motoki and Ryuhei Uehara: Unique Solution Instance Generation for the 3-Satisfiability (3SAT) Problem, IEICE Technical Report, COMP98-54, pp.25-32, 1998/11/20. PostScript file (91603 bytes, compressed by gzip).
  69. 元木 光雄、上原 隆平: 3充足可能性判定問題3SATの単一解を持つ正例題生成手法の解析, IEICE Technical Report, COMP97-117, pp.85-92, 1998/3/24. PostScript file (115524 bytes, compressed by gzip).
  70. Ryuhei Uehara: Parallel Complexity of the Lexicographically First Maximal Subgraph Problems on Restricted Graphs, IEICE Technical Report, COMP97-68, pp.65-72, 1997/11/14. PostScript file (71523 bytes, compressed by gzip).
  71. Ryuhei Uehara: A Measure of Parallelization for the Lexicographically First Maximal Independent Set Problem, IPSJ SIG Notes, 97-AL-56, pp.19-26, 1997/3/14. PostScript file (57555 bytes, compressed by gzip).
  72. Ryuhei Uehara, Kensei Tsuchida, and Ingo Wegener: Optimal attribute-efficient learning of disjunction, parity, and threshold functions, Electronic Colloquium on Computational Complexity(ECCC), Report TR96-061, 1996.
  73. Ryuhei Uehara: NP-completeness of the problems on a restricted graph, Tokyo Woman's Christian University, Technical Report TWCU-M-0004, 1996/9. PostScript file (45645 bytes, compressed by gzip).
  74. Ryuhei Uehara, and Kensei Tsuchida: Partial Gates and Their Identifications, 情報基礎理論ワークショップ, 1996/7/18. IEICE Technical Report, COMP96-22, pp.1-10, 1996/7/25. PostScript file (63810 bytes, compressed by gzip).
  75. Ryuhei Uehara, Zhi-Zhong Chen, and Xin He: 極大パス集合に対する効率的な並列アルゴリズムとその応用, IPSJ SIG Notes, 96-AL-51, pp.25-32, 1996/5/29. PostScript file can be found in the page of conferences.
  76. Ryuhei Uehara, Zhi-Zhong Chen, and Xin He: RNC and NC Algorithms for Maximal Path Sets and Applications to Superstrings with Flipping, 計算モデルと計算の複雑さに関する研究(京大数解研講究録), Research Institute for Mathematical Sciences, Vol. 950, pp.113-119, 1996/2/1. PostScript file can be found in the page of conferences.
  77. Ryuhei Uehara: Complexity Classes Characterized by Many Computation Paths, 情報基礎理論ワークショップ, 1995/7/19. IEICE Technical Report, COMP95-42, pp.9-15, 1995/9/22. PostScript file (59125 bytes, compressed by gzip).
  78. Ryuhei Uehara: Complexity Classes Characterized by Semi-Random Sources, Fundamental Studies on Computational Complexity (京大数解研講究録), Research Institute for Mathematical Sciences, Vol. 943, pp.1-14, 1995/6/14. PostScript file (73656 bytes, compressed by gzip).
  79. Ryuhei Uehara: Efficient Simulations by a Biased Coin, 情報基礎理論ワークショップ, pp.13-16, 1994/7/18. PostScript file can be found in the page of papers.
  80. Ryuhei Uehara: A New Proof for the Monte Carlo Constructibility of loglog n, Tokyo Woman's Christian University, Technical Report TWCU-M-0002, 1994/8. PostScript file (48167 bytes, compressed by gzip).
  81. 上原隆平: 確率Turing Machineにおける低いレベルの領域強構成可能性について, 情報基礎理論ワークショップ, pp.16-21, 1993/7/14. PostScript file (79599 bytes, compressed by gzip).
  82. 上原隆平: log(k)n の領域強構成可能性について, IEICE Technical Report, COMP93-38, pp.59-67, 1993/7/13.
  83. 上原隆平、柴山茂樹、吉本雅彦、黒沢貴弘: オブジェクトの『所有者モデル』とC++による実装例, 情報処理学会全国大会, 4:pp.109-110, 1993/3/24.
  84. 上原隆平、岩田茂樹: 一般化Hi-QのNP完全性について, IEICE Technical Report, COMP89-31, pp.47-54, 1989/7/26.
  85. 上原隆平、岩田茂樹: 一人ゲームHi-Q:その判定の困難さ と発見的探索法, 情報基礎理論ワークショップ, 1989/1/31.
  86. 上原隆平、岩田茂樹: 一人ゲームHi-Qについて, 情報基礎理論セミナー, pp.19-20, 1989/1/28.
Last modified: Fri Nov 19 10:57:04 JST 2010
by R.Uehara (uehara@jaist.ac.jp) 		Valid HTML 4.0!