Journal Papers by R. Uehara

  1. Giuseppe Antonio Di Luna, Ryuhei Uehara, Giovanni Viglietta, and Yukiko Yamauchi. Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots, Theoretical Computer Science, accepted, 2024.
  2. Takumi Shiota, Tonan Kamata, and Ryuhei Uehara. Overlapping of Lattice Unfolding for Cuboids, IEICE Transactions on Information and Systems, Vol. E108-D,No.3,pp. ??-??, Mar. 2025.
  3. Rin Saito, Hiroshi Eto, Takehiro Ito, and Ryuhei Uehara. Reconfiguration of vertex-disjoint shortest paths on graphs, Journal of Graph Algorithms and Applications, Vol. 28, No. 3, pp.87-101, September 2024. DOI:10.7155/jgaa.v28i3.2973
  4. Masaaki Kanzaki, Yota Otachi, Giovanni Viglietta, Ryuhei Uehara. Computational Complexity of Jumping Block Puzzles, Theoretical Computer Science, accepted, January 2024.
  5. Kazuaki Yamazaki, Mengze Qian, and Ryuhei Uehara. Efficient Enumeration of Non-isomorphic Distance-Hereditary Graphs and Related Graphs, Discrete Applied Mathematics, Vol. 342, pp. 190-199, January 2024. DOI:10.1016/j.dam.2023.09.002
  6. Yiyang Jia, Jun Mitani and Ryuhei Uehara. Clarifying the Difference between Origami Fold Models by a Matrix Representation, Thai Journal of Mathematics, pp. 1061-1079 , Vol. 21, No. 4, December 2023.
  7. Kota Chida, Erik D. Demaine, Martin L. Demaine, David Eppstein, Adam Hesterberg, Takashi Horiyama, John Iacono, Hiro Ito, Stefan Langerman, Ryuhei Uehara, and Yushi Uno. Multifold Tiles of Polyominoes and Convex Lattice Polygons, Thai Journal of Mathematics, pp. 957-978 ,Vol. 21, No. 4, December 2023.
  8. Ryuhei Uehara. Computational Complexity of Puzzles and Related Topics, Interdisciplinary Information Sciences, Vol. 29, No. 2, pp. 119-140, December 2023. DOI:10.4036/iis.2022.R.06
  9. Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka, and Toshiki Saitoh. Sorting Balls and Water: Equivalence and Computational Complexity, Theoretical Computer Science, Vol. 978, 114158(15 pages), November 2023. DOI:10.1016/j.tcs.2023.114158
  10. Erik D. Demaine, Martin L. Demaine, Yevhenii Diomidov, Tonan Kamata, Ryuhei Uehara, and Hanyu Alice Zhang. Any Platonic Solid Can Transform to Another by O(1) Refoldings, Computational Geometry: Theory and Applications, Vol. 113, 101995(13 pages), August 2023.
  11. Ko Minamisawa, Ryuhei Uehara, and Masao Hara. Mathematical Characterizations and Computational Complexity of Anti-Slide Puzzles, Theoretical Computer Science, Vol. 939, pp. 216-226, January 2023. DOI:10.1016/j.tcs.2022.10.026
  12. Yui Uehara, Satoshi Tojo, and Ryuhei Uehara. Unsupervised Discovery of Tonality in Bach's Chorales, Journal of Intelligence Informatics and Smart Technology, Vol. 8, pp. 10:1-10:7, October 2022.
  13. Win Hlaing Hlaing Myint, Ryuhei Uehara, and Giovanni Viglietta. Token Shifting on Graphs, International Journal of Computer Mathematics: Computer Systems Theory, Vol. 7:4, pp. 223--234, September 2022. DOI:10.1080/23799927.2022.2118622
  14. Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara. Developing a tetramonohedron with minimum cut length, Computational Geometry: Theory and Applications, Vol. 108, 101903(11 pages), June 2022. DOI:10.1016/j.comgeo.2022.101903
  15. Yiyang Jia, Jun Mitani, and Ryuhei Uehara. Logical Matrix Representations in Map Folding, IEICE Trans., Vol.E105-A, No.10, pp. 1401-1412, October 2022.
  16. Tonan Kamata, Akira Kadoguchi, Takashi Horiyama, and Ryuhei Uehara. Efficient Folding Algorithms for Convex Polyhedra, Discrete & Computational Geometry, accepted (24 pages), 2022. DOI:10.1007/s00454-022-00415-7
  17. Takashi Horiyama, Fabian Klute, Matias Korman, Irene Parada, Ryuhei Uehara, and Katsuhisa Yamanaka. Efficient Segment Folding is Hard, Computational Geometry: Theory and Applications, Vol. 104, 101860:1-13, June 2022. DOI:10.1016/j.comgeo.2022.101860
  18. Hugo A. Akitaya, Erik D. Demaine, David Eppstein, Tomohiro Tachi, and Ryuhei Uehara. Ununfoldable Polyhedra with 6 Vertices or 6 Faces, Computational Geometry: Theory and Applications, Vol. 103, 101857 (8 pages), April 2022. DOI:10.1016/j.comgeo.2021.101857
  19. Feng Tianfeng, Giovanni Vigliette, and Ryuhei Uehara. Bicolored Path Embedding Problems in Protein Folding Models, IEICE Trans., Vol. E105-D, No. 3, pp. 623-633, March 2022. DOI:10.1587/transinf.2021EDP7206
  20. Kwon Kham Sai, Ryuhei Uehara, and Giovanni Viglietta. Cyclic Shift Problems on Graphs, IEICE Trans., Vol. E105-D, No. 3, pp. 532-540, March 2022. DOI:10.1587/transinf.2021FCP0010
  21. Tamami Okada and Ryuhei Uehara. Research on dissections of a net of a cube into nets of cubes, IEICE Trans. on Inf. and Sys., Vol. E105-D, No. 3, pp. 459-465, March 2022. DOI:10.1587/transinf.2021FCP0004
  22. Katsuhisa Yamanaka, David Avis, Takashi Horiyama, Yoshio Okamoto, Ryuhei Uehara, and Tanami Yamauchi. Algorithmic Enumeration of Surrounding Polygons, Discrete Applied Mathematics, Volume 303, pp. 305-313, November 2021. DOI:10.1016/j.dam.2020.03.034
  23. Yiyang Jia, Jun Mitani, and Ryuhei Uehara. Research on Map Folding with Boundary Order on Simple Fold, IEICE Trans., Vol. E104-A, No. 9, pp. 1116-1126, September 2021. DOI:10.1587/transfun.2020DMP0017
  24. Takashi Horiyama, Shin-ichi Nakano, Toshiki Saitoh, Koki Suetsugu, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, and Kunihiro Wasa. Max-Min 3-dispersion Problems, IEICE Trans., Vol. E104-A, No. 9, pp. 1101-1107, September 2021. DOI:10.1587/transfun.2020DMP0003
  25. Takeshi Yamada and Ryuhei Uehara. Shortest Reconfiguration of Sliding Tokens on Subclasses of Interval Graphs, Theoretical Computer Science, Vol. 863, pp. 53-68, April 2021. DOI:10.1016/j.tcs.2021.02.019
  26. Martin L. Demaine, Robert Hearn, Junnosuke Hoshido, Jason Ku, and Ryuhei Uehara. Rectangular Unfoldings of Polycubes, Journal of Information Processing, Vol. 28, pp. 841-845, December, 2020. DOI:10.2197/ipsjjip.28.841
  27. Yiyang Jia, Jun Mitani, and Ryuhei Uehara. Valid Orderings of Layers When Simple-Folding a Map. Journal of Information Processing, Vol. 28, pp. 816-824, December, 2020. (JIP Specially selected paper) DOI:10.2197/ipsjjip.28.816
  28. Yiyang Jia, Jun Mitani, and Ryuhei Uehara. Efficient Algorithm for 2×n Map Folding with a Box-pleated Crease Pattern. Journal of Information Processing, Vol. 28, pp. 806-815, December, 2020. DOI:10.2197/ipsjjip.28.806
  29. Koji Ouchi and Ryuhei Uehara. Minimum Forcing Sets for Single-vertex Crease Pattern. Journal of Information Processing, Vol. 28, pp. 800-805, December, 2020. DOI:10.2197/ipsjjip.28.800
  30. Eiji Miyano, Toshiki Saitoh, Ryuhei Uehara, Tsuyoshi Yagita, and Tom C. van der Zanden. Complexity of the Maximum k-Path Vertex Cover Problem, IEICE Trans. Fundamentals, Vol. E103-A, No. 10, pp. 1193-1201, October, 2020. DOI:10.1587/transfun.2019DMP0014
  31. Takehiro Ito, Marcin Kamiński, Hirotaka Ono, Akira Suzuki, Ryuhei Uehara, and Katsuhisa Yamanaka. Parameterized Complexity of Independent Set Reconfiguration Problems, Discrete Applied Mathematics, Vol. 283, pp. 336-345, September, 2020. DOI:10.1016/j.dam.2020.01.022
  32. Koichi Mizunashi, Takashi Horiyama, and Ryuhei Uehara. Efficient Algorithm for Box Folding, Journal of Graph Algorithms and Applications, Vol. 24, No. 2, pp. 89-103, February, 2020. DOI:10.7155/jgaa.00520
  33. Kazuaki Yamazaki, Toshiki Saitoh, Masashi Kiyomi, and Ryuhei Uehara. Enumeration of Nonisomorphic Interval Graphs and Nonisomorphic Permutation Graphs, Theoretical Computer Science, Vol. 806, pp. 323-331, January, 2020. DOI:10.1016/j.tcs.2019.04.017
  34. Erik D. Demaine, Matias Korman, Jason S. Ku, Joseph S. B. Mitchell, Yota Otachi, Andre van Renssene, Marcel Roeloffzen, Ryuhei Uehara, and Yushi Uno. Symmetric Assembly Puzzles are Hard, Beyond a Few Pieces, Computational Geometry: Theory and Applications, Vol. 90, pp. 101648:1-11, 2020. DOI:10.1016/j.comgeo.2020.101648
  35. Takumu Shirayama, Takuto Shigemura, Yota Otachi, Shuichi Miyazaki, and Ryuhei Uehara. On Computational Complexity of Pipe Puzzles, IEICE Trans. on Inf. and Sys., Vol. E102-A, No.9, pp. 1134-1141, September 2019. DOI:10.1587/transfun.E102.A.1134
  36. Katsuhisa Yamanaka, Erik D. Demaine, Takashi Horiyama, Akitoshi Kawamura, Shin-ichi Nakano, Yoshio Okamoto, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, and Takeaki Uno. Sequentially Swapping Colored Tokens on Graphs, Journal of Graph Algorithms and Applications, Vol. 23, no. 1, pp. 3-27, September 2019. DOI:10.7155/jgaa.00482, JAIST Repository
  37. Koji Ouchi and Ryuhei Uehara. Efficient Enumeration of Flat-Foldable Single Vertex Crease Patterns, IEICE Trans. on Inf. and Sys., Vol. E102-D, No.3, pp. 416-422, Mar. 2019. JAIST Repository
  38. Katsuhisa Yamanaka, Takashi Horiyama, J. Mark Keil, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno. Swapping Colored Tokens on Graphs, Theoretical Computer Science, Vol. 729, pp. 1-10, June, 2018. DOI:10.1016/j.tcs.2018.03.016, arXiv:1803.06816. JAIST Repository
  39. Zachary R. Abel, Erik D. Demaine, Martin L. Demaine, David Eppstein, Anna Lubiw, and Ryuhei Uehara. Flat foldings of plane graphs with prescribed angles and edge lengths, Journal of Computational Geometry, Vol. 9, No. 1, pp. 71-91, 2018. DOI:10.20382/jocg.v9i1a3, JAIST Repository
  40. Zachary R. Abel, Erik D. Demaine, Martin L. Demaine, Hiro Ito, Jack Snoeyink, and Ryuhei Uehara. Bumpy Pyramid Folding, COMPUTATIONAL GEOMETRY: Theory and Applications, Vol 75, pp. 22-31, December 2018. DOI:10.1016/j.comgeo.2018.06.007
  41. Dawei Xu, Jinfeng Huang, Yuta Nakane, Tomoo Yokoyama, Takashi Horiyama, and Ryuhei Uehara. Rep-cubes: Dissection of a Cube into Nets, IEICE Trans. on Inf. and Sys., Vol. E101-A, No.9, pp. 1420-1430, Sep. 2018. DOI:10.1587/transfun.E101.A.1420
  42. Hitoshi Iwai, Jungo Shibuya, Kokolo Ikeda, and Ryuhei Uehara. Convex Configurations of Tangram-type Puzzles, Cubism For Fun, Vol. 104, pp.32-38, November 2017.
  43. Zach Abel, Brad Ballinger, Erik D. Demaine, Martin L. Demaine, Jeff Erickson, Adam Hesterberg, Hiro Ito, Irina Kostitsyna, Jayson Lynch, and Ryuhei Uehara. Unfolding and Dissection of Multiple Cubes, Tetrahedra, and Doubly Covered Squares, Journal of Information Processing, Vol.25, pp. 610-615, August 2017. JAIST Repository
  44. Takashi Horiyama, Takashi Iizuka, Masashi Kiyomi, Yoshio Okamoto, Ryuhei Uehara, Takeaki Uno, Yushi Uno, and Yukiko Yamauchi. Sankaku-Tori: An Old Western-Japanese Game Played on a Point Set, Journal of Information Processing, Vol.25, pp. 708-715, August 2017. JAIST Repository
  45. Takashi Horiyama, Takehiro Ito, Keita Nakatsuka, Akira Suzuki, and Ryuhei Uehara. Complexity of tiling a polygon with trominoes or bars, Discrete and Computational Geometry, Vol. 58(3), pp. 686-704, October 2017. DOI:10.1007/s00454-017-9884-9 JAIST Repository
  46. Dawei Xu, Takashi Horiyama, Toshihiro Shirakawa, and Ryuhei Uehara. Common Developments of Three Incongruent Boxes of Area 30, COMPUTATIONAL GEOMETRY: Theory and Applications, Vol. 64, pp. 1-17, August 2017. DOI:10.1016/j.comgeo.2017.03.001
  47. Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, and Ryuhei Uehara. Ferrers dimension of grid intersection graphs, Discrete Applied Mathematics, Vol. 216, No. 1, pp. 130-135, January, 2017. DOI:10.1016/j.dam.2015.05.035
  48. Eli Fox-Epstein, Kazuho Katsumata, and Ryuhei Uehara. The Convex Configurations of ``Sei Shonagon Chie no Ita,'' Tangram, and Other Silhouette Puzzles with Seven Pieces, IEICE Trans. on Inf. and Sys., Vol.E99-A, No.6, pp.1084-1089, June, 2016. DOI:10.1587/transfun.E99.A.1084, JAIST Repository
  49. Yoshiaki Araki, Takashi Horiyama, and Ryuhei Uehara. Common Unfolding of Regular Tetrahedron and Johnson-Zalgaller Solid, Journal of Graph Algorithms and Applications, Vol.20, no.1, pp.101-114, February, 2016. DOI:10.7155/jgaa.00386, JAIST Repository
  50. Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno. A polynomial-time approximation scheme for the geometric unique coverage problem on unit squares, COMPUTATIONAL GEOMETRY: Theory and Applications, Vol. 51 pp. 25-39, January, 2016. DOI:10.1016/j.comgeo.2015.10.004, JAIST Repository
  51. Erik D. Demaine, David Eppstein, Adam Hesterberg, Hiro Ito, Anna Lubiw, Ryuhei Uehara, and Yushi Uno. Folding a Paper Strip to Minimize Thickness, Journal of Discrete Algorithms, Vol. 36, pp. 18-26, January, 2016. 10.1016/j.jda.2015.09.003 JAIST Repository
  52. Matsuo Konagaya, Yota Otachi, and Ryuhei Uehara. Polynomial-time algorithms for Subgraph Isomorphism in small graph classes of perfect graphs, Discrete Applied Mathematics, Vol. 199, pp.37-45, January, 2016. DOI:10.1016/j.dam.2015.01.040. JAIST Repository
  53. Erik D Demaine, Martin L Demaine, Eli Fox-Epstein, Duc A Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, and Takeshi Yamada. Linear-Time Algorithm for Sliding Tokens on Trees, Theoretical Computer Science, Vol. 600, pp. 132-142, October 2015. DOI:10.1016/j.tcs.2015.07.037 JAIST Repository
  54. Kazuyuki Amano, Kyaw May Oo, Yota Otachi, and Ryuhei Uehara. Secure Sets and Defensive Alliances in Graphs: A Faster Algorithm and Improved Bounds, IEICE Trans. on Inf. and Sys., Vol.E98-D, No.3, pp.486-489, March, 2015. JAIST Repository
  55. Oswin Aichholzer, Jean Cardinal, Thomas Hackl, Ferran Hurtado, Matias Korman, Alexander Pilz, Rodrigo Silveira, Ryuhei Uehara, Pavl Valtr, Birgit Vogtenhuber, Emo Welzl. Cell-Paths in Mono- and Bichromatic Line Arrangements in the Plane, Discrete Mathematics and Theoretical Computer Science, Vol. 16, No. 3, pp. 317-332, December, 2014. JAIST Repository
  56. Ryuhei Uehara: The graph isomorphism problem on geometric graphs, Discrete Mathematics and Theoretical Computer Science, Vol 16, No. 2, pp. 87-96, October, 2014.
  57. Colin Cooper, Alan Frieze, and Ryuhei Uehara. The height of random k-trees and related branching processes, Random Structure & Algorithms, Vol 45, No. 4, pp. 675-702, October, 2014.
  58. Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, and Takeaki Uno. Base-Object Location Problems for Base-Monotone, Theoretical Computer Science, Vol. 555, pp. 71-84, October 2014. DOI:10.1016/j.tcs.2013.11.030. JAIST Repository
  59. Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, and Yushi Uno. A 4.31-Approximation for the Geometric Unique Coverage Problem on Unit Disks, Theoretical Computer Science, Vol. 544, pp. 14-31, August, 2014. DOI:10.1016/j.tcs.2014.04.014, JAIST Repository
  60. Erik D. Demaine, Yoshio Okamoto, Ryuhei Uehara, and Yushi Uno. Computational complexity and an integer programming model of Shakashaka, IEICE Transactions, Vol. E97-A, No.6, pp. 1213-1219, June 2014. JAIST Repository
  61. Zachary Abel, Erik D. Demaine, Martin L. Demaine, Takashi Horimaya, and Ryuhei Uehara. Computational Complexity of Piano-Hinged Dissections, IEICE Transactions, Vol. E97-A, No.6, pp. 1206-1212, June 2014. JAIST Repository
  62. Erik D. Demaine, Martin L. Demaine, Nicholas J. A. Harvey, Ryuhei Uehara, Takeaki Uno, Yushi Uno. UNO is hard, even for a single player, Theoretical Computer Science, Vol. 521, pp. 51-61, February 2014. DOI:10.1016/j.tcs.2013.11.023. JAIST Repository
  63. Toshihiro Shirakawa and Ryuhei Uehara. Common Developments of Three Incongruent Orthogonal Boxes, International Journal of Computational Geometry and Applications, Vol. 23, No. 1, pp. 65-71, 2013. DOI:10.1142/S0218195913500040.
  64. Takeaki Uno, Ryuhei Uehara, and Shin-ichi Nakano. Bounding the Number of Reduced Trees, Cographs, and Series-Parallel Graphs by Compression, Discrete Mathematics, Algorithms and Applications, Vol. 5, No. 2, pp. 1360001-1350014, 2013. JAIST Repository
  65. Ryuhei Uehara. Tractabilities and Intractabilities on Geometric Intersection Graphs, Algorithms, Vol. 6, No. 1, pp. 60-83, 2013.
  66. Shin-ichi Nakano, Ryuhei Uehara, and Takeaki Uno. Efficient algorithms for a simple network design problem, Networks, Vol. 62, No. 2, pp. 95-104, 2013.
  67. Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara. Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs, IEICE Trans. Inf. & Syst., Vol. E96-D, No.3,pp. 426-432, Mar. 2013.
  68. Brad Ballinger, Nadia Benbernou, Prosenjit Bose, Mirela Damian, Erik D. Demaine, Vida Dujmović, Robin Flatland, Ferran Hurtado, John Iacono, Anna Lubiw, Pat Morin, Vera Sacristán, Diane Souvaine, and Ryuhei Uehara. Coverage with k-Transmitters in the Presence of Obstacles, Journal of Combinatorial Optimization, Vol. 25(2), pp. 208-233, February, 2013. DOI:10.1007/s10878-012-9475-x
  69. Takehiro Ito, Yuichiro Miyamoto, Hirotaka Ono, Hisao Tamaki, and Ryuhei Uehara. Route-Enabling Graph Orientation Problems, Algorithmica, Vol. 65, pp. 317-338, Feburary, 2013. DOI:10.1007/s00453-011-9589-z, JAIST Repository.
  70. Takuya Umesato, Toshiki Saitoh, Ryuhei Uehara, Hiro Ito, and Yoshio Okamoto. Complexity of the stamp folding problem, Theoretical Computer Science, Vol. 497, pp. 13-19, 2012. DOI:10.1016/j.tcs.2012.08.006
  71. Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara. Bipartite Permutation Graphs are Reconstructible, Discrete Mathematics, Algorithms and Applications, Vol. 4, No. 3, pp. 1250039:1-14, August, 2012. DOI:10.1142/S1793830912500395
  72. Tetsuo Asano, Jesper Jansson, Kunihiko Sadakane, Ryuhei Uehara, and Gabriel Valiente. Faster Computation of the Robinson-Foulds Distance between Phylogenetic Networks, Information Sciences, Vol. 197, pp. 77-90, August, 2012. DOI:10.1016/j.ins.2012.01.038
  73. Yosuke Okayama, Masashi Kiyomi, and Ryuhei Uehara. On Covering of Any Point Configuration by Disjoint Unit Disks, Geombinatorics, vol. XXI(1), pp.14-23, July, 2012.
  74. Tetsuo Asano, Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara. NP-completeness of generalized Kaboozle, Journal of Information Processing, Vol. 20, No. 3, pp. 713-718, July, 2012. JAIST Repository
  75. Yoshio Okamoto, Yota Otachi, and Ryuhei Uehara. On bipartite powers of bigraphs, Discrete Mathematics and Theoretical Computer Science, Vol. 14, No.2, pp.11-20, July, 2012. JAIST Repository
  76. David Charlton, Erik D. Demaine, Martin L. Demaine, Vida Dujmović, Pat Morin, and Ryuhei Uehara. Ghost Chimneys, International Journal of Computational Geometry and Applications , Vol. 22, No. 3, pp. 207-214, June, 2012. DOI:10.1142/S0218195912500057, JAIST Repository
  77. Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara. Any Monotone Function is Realized by Interlocked Polygons, Algorithms, Vol. 5(1), pp. 148-157, March, 2012. DOI:10.3390/a5010148 JAIST Repository
  78. Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, and Ryuhei Uehara. Random Generation and Enumeration of Bipartite Permutation Graphs, Journal of Discrete Algorithms, Vol. 10, pp. 84-97, January, 2012. DOI:10.1016/j.jda.2011.11.001 JAIST Repository
  79. Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, and Takeaki Uno. Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem, Journal of Graph Algorithms and Applications, Vol. 15, No. 6, pp. 727-751, 2011. JAIST Repository DOI:10.7155/jgaa.00246
  80. Sachio Teramoto, Erik D. Demaine, and Ryuhei Uehara. Voronoi game on graphs and its complexity, Journal of Graph Algorithms and Applications, Vol. 15, No. 4, pp. 485-501, 2011. JAIST Repository (A preliminary version was presented at 2nd IEEE Symposium on Computational Intelligence and Games (CIG 2006).) DOI:10.7155/jgaa.00235
  81. Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara. Voronoi Game on a Path, IEICE Trans. Inf. & Syst., Vol. E94-D, pp. 1185-1189, 2011. DOI:10.1587/transinf.E94.D.1185
  82. Jean Cardinal, Erik D. Demaine, Martin L. Demaine, Shinji Imahori, Tsuyoshi Ito, Masashi Kiyomi, Stefan Langerman, Ryuhei Uehara, and Takeaki Uno. Algorithmic Folding Complexity, Graphs and Combinatorics, Vol. 27, pp. 341-351, 2011. DOI:10.1007/s00373-011-1019-0
  83. 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, Theoretical Computer Science, Vol. 412, pp. 1054-1065, 2010. DOI:10.1016/j.tcs.2010.12.005, JAIST Repository
  84. Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara. Reconstruction of Interval Graphs, Theoretical Computer Science, Vol. 411, pp.3859-3866, 2010. DOI:10.1016/j.tcs.2010.07.006
  85. Yasuko Matsui, Ryuhei Uehara, and Takeaki Uno. Enumeration of the Perfect Sequences of a Chordal Graph, Theoretical Computer Science, Vol. 411(40-42), pp. 3635-3641, 2010. DOI:10.1016/j.tcs.2010.06.007
  86. Toshiki Saitoh, Katsuhisa Yamanaka, Masashi Kiyomi and Ryuhei Uehara. Random Generation and Enumeration of Proper Interval Graphs IEICE Transactions, Vol. E93-D, No. 7, pp. 1816-1823, 2010. DOI:10.1587/transinf.E93.D.1816 (A preliminary version was presented at WALCOM 2009.)
  87. Katsuhisa Yamanaka, Shin-ichi Nakano, Yasuko Matsui, Ryuhei Uehara, and Kento Nakada. Efficient Enumeration of All Ladder Lotteries and Its Application, Theoretical Computer Science, Vol. 411, pp. 1714-1722, 2010. DOI:10.1016/j.tcs.2010.01.002
  88. Colin Cooper and Ryuhei Uehara. Scale free properties of random k-trees, Mathematics in Computer Science, Vol. 3(4), pp. 489-496, 2010. DOI:10.1007/s11786-010-0041-6
  89. Naoto Miyoshi, Mariko Ogura, Takeya Shigezumi and Ryuhei Uehara. Subexponential interval graphs generated by immigration-death process, Probability in the Engineering and Informational Sciences, 24:289-301, 2010. DOI:10.1017/S0269964809990283 (A preliminary version was presented at IWAP 2008.)
  90. Naoto Miyoshi, Takeya Shigezumi, Ryuhei Uehara, Osamu Watanabe. Scale Free Interval Graphs, Theoretical Computer Science, Vol. 410(45), pp. 4533-4600, 2009. DOI:10.1016/j.tcs.2009.08.012 (A preliminary version was presented at AAIM 2008.)
  91. Shin-ichi Nakano, Ryuhei Uehara and Takeaki Uno. A New Approach to Graph Recognition and Applications to Distance-Hereditary Graphs, Journal of Computer Science and Technology, Vol. 24(3), pp. 517-533, 2009. (A preliminary version was presented at TAMC 2007.)
  92. Ryuhei Uehara and Yushi Uno. Laminar Structure of Ptolemaic Graphs with Applications, Discrete Applied Mathematics, Vol. 157(7), pp. 1533-1543, 2009. DOI:10.1016/j.dam.2008.09.006 (A preliminary version was presented at ISAAC 2005.)
  93. Yoshio Okamoto, Takeaki Uno, and Ryuhei Uehara. Counting the Number of Independent Sets in Chordal Graphs, Journal of Discrete Algorithms, Vol. 6/2, pp. 229-242, 2008. DOI:10.1016/j.jda.2006.07.006 (A preliminary version was presented at WG 2005.)
  94. Yoshihiro Takahara, Sachio Teramoto, and Ryuhei Uehara. Longest Path Problems on Ptolemaic Graphs, IEICE Transactions, E91-D, No. 2, pp. 170-177, 2008. DOI:10.1093/ietisy/e91-d.2.170 (A preliminary version was presented at KyotoCGGT 2007.)
  95. Ryuhei Uehara and Yushi Uno. On Computing Longest Paths in Small Graph Classes, International Journal of Foundations of Computer Science, 18(5), pp.911-930, 2007. DOI:10.1142/S0129054107005054 (PDF file(193110 bytes)) (A preliminary version waspresented at ISAAC 2004.)
  96. Ryuhei Uehara and Gabriel Valiente. Linear Structure of Bipartite Permutation Graphs with an Application, Information Processing Letters, 103(2), pp.71-77, 2007. DOI:10.1016/j.ipl.2007.02.010 (PDF file(189330 bytes))
  97. Andreas Brandstädt, Feodor F. Dragan, Hoang-Oanh Le, Van Bang Le, and Ryuhei Uehara. Tree Spanners for Bipartite Graphs and Probe Interval Graphs, Algorithmica, 47(1), pp.27-51, 2007. DOI:10.1007/s00453-006-1209-y. (A preliminary version was presented at WG 2003.)
  98. Ryuhei Uehara, Seinosuke Toda and Takayuki Nagoya. Graph Isomorphism Completeness for Chordal Bipartite Graphs and Strongly Chordal Graphs, Discrete Applied Mathematics, 145(3), pp.479-482, 2005. PDF file(142547 bytes). DOI:10.1016/j.dam.2004.06.008.
  99. Peisen Zhang, Huitao Sheng, and Ryuhei Uehara. A Double Classification Tree Search Algorithm for Index SNP Selection, BMC Bioinformatics, 5:89, 2004. DOI:10.1186/1471-2105-5-89.
  100. Ryuhei Uehara and Zhi-Zhong Chen. Parallel Approximation Algorithms for Maximum Weighted Matching in General Graphs, Information Processing Letters, 76, pp.13-17, 2000. Full version was presented at IFIP TCS2000. DOI:10.1016/S0020-0190(00)00128-9.
  101. Mitsuo Motoki and Ryuhei Uehara. Unique Solution Instance Generation for the 3-Satisfiability (3SAT) Problem, In SAT2000 edited by I. Gent, H. van Maaren, and T. Walsh, pp.293-307, IOS Press, 2000. See Research Report C-129, Dept. of Math. and Computing Sciences, Tokyo Inst. of Tech., 1999.
  102. Ryuhei Uehara, Kensei Tsuchida, and Ingo Wegener. Identification of Partial Disjunction, Parity, and Threshold Functions, Theoretical Computer Science, Vol. 230, pp. 131-147, 2000. PostScript file (72727 bytes, compressed by gzip). (A preliminary version was presented at EuroCOLT '97.) DOI:10.1016/S0304-3975(99)00154-1.
  103. Ryuhei Uehara. A Measure for the Lexicographically First Maximal Independent Set Problem and Its Limits, International Journal of Foundations of Computer Science, Vol.10, No.4, pp.473-482,1999. PostScript file (56060 bytes, compressed by gzip). (The former half was presented at WG '97, and the latter half was presented at I-SPAN '99.) DOI:10.1142/S0129054199000332
  104. Ryuhei Uehara, Zhi-Zhong Chen, and Xin He. Fast RNC and NC Algorithms for Maximal Path Sets , Theoretical Computer Science, Vol. 215, pp. 89-98, 1999. A preliminary version was presented at CoCoon '96. DOI:10.1016/S0304-3975(97)00132-1.
  105. Ryuhei Uehara and Zhi-Zhong Chen. Parallel Algorithms for Maximal Linear Forests, The TRANSACTIONS of the IEICE, E80-A, pp.627-634, 1997. A preliminary version was presented at IPPS '97.
  106. Ryuhei Uehara. Collapse of PP with a Semi-Random Source to BPP, Information Processing Letters, 61, pp.83-87, 1997. PostScript file (52943 bytes, compressed by gzip). DOI:10.1016/S0020-0190(96)00201-3.
  107. Ryuhei Uehara. Efficient Simulations by a Biased Coin, Information Processing Letters, 56,Dec.,pp.245-248, 1995. PostScript file (39051 bytes, compressed by gzip). DOI:10.1016/0020-0190(95)00171-2.
  108. Ryuhei Uehara and Shigeki Iwata. Generalized Hi-Q is NP-complete, The TRANSACTIONS of the IEICE, E73,Feb.,pp.270-273,1990. Chapter 7 of my Ph.D thesis contains this result (gzipped PostScript file, 47487bytes).
Last modified: Mon Apr 27 10:17:57 JST 2015
by R.Uehara (uehara@jaist.ac.jp) 		Valid HTML 4.0!