Papers by R. Uehara

  1. Toshihiro Shirakawa and Ryuhei Uehara: Common Developments of Three Incongruent Orthogonal Boxes, International Journal of Computational Geometry and Applications, accepted, 2013.
  2. 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), accepted, 2013.
  3. Ryuhei Uehara: Tractabilities and Intractabilities on Geometric Intersection Graphs, Algorithms, accepted, 2013.
  4. Shin-ichi Nakano, Ryuhei Uehara, and Takeaki Uno: Efficient algorithms for a simple network design problem, Networks, accepted, 2013.
  5. Takuya Umesato, Toshiki Saitoh, Ryuhei Uehara, Hiro Ito, and Yoshio Okamoto: Complexity of the stamp folding problem, Theoretical Computer Science, accepted, 2012. DOI:10.1016/j.tcs.2012.08.006
  6. Masashi Kiyomi, Toshiki Saitoh, and Ryuhei Uehara: Reconstruction Algorithms for Permutation Graphs and Distance-Hereditary Graphs, IEICE Trans. Inf. & Syst., accepted, 2012.
  7. 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
  8. 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
  9. 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
  10. 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.
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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).)
  19. 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
  20. 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
  21. 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
  22. 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
  23. 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
  24. 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.)
  25. 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
  26. 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
  27. 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.)
  28. 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.)
  29. 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.)
  30. 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.)
  31. 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.)
  32. 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.)
  33. 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.)
  34. 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))
  35. 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.)
  36. 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.
  37. 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.
  38. 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.
  39. 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.
  40. 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.
  41. 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
  42. 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.
  43. 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.
  44. 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.
  45. 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.
  46. 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: Thu Dec 23 21:31:38 JST 2010
by R.Uehara (uehara@jaist.ac.jp) 		Valid HTML 4.0!