Papers by R. Uehara

  1. Yoshiaki Araki, Takashi Horiyama, and Ryuhei Uehara: Common Unfolding of Regular Tetrahedron and Johnson-Zalgaller Solid, Journal of Graph Algorithms and Applications, accepted, 2016.
  2. 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., accepted, 2016.
  3. 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, 2016. 10.1016/j.jda.2015.09.003
  4. 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, 2016. DOI:10.1016/j.comgeo.2015.10.004
  5. 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
  6. Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, and Ryuhei Uehara: Ferrers dimension of grid intersection graphs, Discrete Applied Mathematics, DOI:10.1016/j.dam.2015.05.035, 2015.
  7. 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.
  8. 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, 2015.
  9. 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
  10. Ryuhei Uehara: The graph isomorphism problem on geometric graphs, Discrete Mathematics and Theoretical Computer Science, Vol 16, No. 2, pp. 87-96, October, 2014.
  11. 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.
  12. 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
  13. 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
  14. 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.
  15. 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, 2014. DOI:10.1016/j.tcs.2013.11.030
  16. 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, 2014. DOI:10.1016/j.tcs.2013.11.023. JAIST Repository
  17. 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.
  18. 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 (DMAA), Vol. 5, No. 2, pp. 1360001-1350014, 2013. JAIST Repository
  19. Ryuhei Uehara: Tractabilities and Intractabilities on Geometric Intersection Graphs, Algorithms, Vol. 6, No. 1, pp. 60--83, 2013.
  20. 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.
  21. 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.
  22. 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, Feburary, 2013. DOI:10.1007/s10878-012-9475-x
  23. 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
  24. 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
  25. 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
  26. 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
  27. 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.
  28. 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
  29. 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
  30. 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
  31. 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
  32. 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
  33. 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
  34. 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).)
  35. 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
  36. 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
  37. 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
  38. 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
  39. 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
  40. 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.)
  41. 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
  42. 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
  43. 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.)
  44. 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.)
  45. 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.)
  46. 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.)
  47. 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.)
  48. 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.)
  49. 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.)
  50. 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))
  51. 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.)
  52. 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.
  53. 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.
  54. 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.
  55. 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.
  56. 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.
  57. 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
  58. 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.
  59. 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.
  60. 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.
  61. 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.
  62. 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!