Yota Otachi

Refereed Papers in Journals

  1. Tesshu Hanaka, Hirotaka Ono, Yota Otachi, Saeki Uda.
    Grouped domination parameterized by vertex cover, twin cover, and beyond.
    Theoretical Computer Science 996, 114507, May 2024.
  2. Yuuki Aoike, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi.
    Finding a reconfiguration sequence between longest increasing subsequences.
    IEICE Transactions E107-D, 559-563, April 2024.
  3. Tesshu Hanaka, Nicolás Honorato Droguett, Kazuhiro Kurita, Hirotaka Ono, Yota Otachi.
    Collecting balls on a line by robots with limited energy.
    IEICE Transactions E107-D, 325-327, March 2024.
  4. Tatsuya Gima, Tesshu Hanaka, Kohei Noro, Hirotaka Ono, Yota Otachi.
    On a spectral lower bound of treewidth.
    IEICE Transactions E107-D, 328-330, March 2024.
  5. Masaaki Kanzaki, Yota Otachi, Giovanni Viglietta, Ryuhei Uehara.
    Computational complexity of jumping block puzzles.
    Theoretical Computer Science 983, 114292, February 2024.
  6. Tatsuya Gima, Yota Otachi.
    Extended MSO model checking via small vertex integrity.
    Algorithmica 86, 147-170, January 2024.
  7. Takehiro Ito, Jun Kawahara, Shin-ichi Minato, Yota Otachi, Toshiki Saitoh, Akira Suzuki, Ryuhei Uehara, Takeaki Uno, Katsuhisa Yamanaka, Ryo Yoshinaka.
    Sorting balls and water: Equivalence and computational complexity.
    Theoretical Computer Science 978, 114158, November 2023.
  8. Takehiro Ito, Hirotaka Ono, Yota Otachi.
    Reconfiguration of cliques in a graph.
    Discrete Applied Mathematics 333, 43-58, July 2023.
  9. Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa.
    Reconfiguring (non-spanning) arborescences.
    Theoretical Computer Science 943, 131-141, January 2023.
  10. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi.
    Grundy distinguishes treewidth from pathwidth.
    SIAM Journal on Discrete Mathematics 36, 1761-1787, August 2022.
  11. Yasuaki Kobayashi, Yota Otachi.
    Parameterized complexity of graph burning.
    Algorithmica 84, 2379-2393, August 2022.
  12. Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi.
    Exploring the gap between treedepth and vertex cover through vertex integrity.
    Theoretical Computer Science 918, 60-76, May 2022.
  13. Yuuki Aoike, Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi.
    An improved deterministic parameterized algorithm for cactus vertex deletion.
    Theory of Computing Systems 66, 502-515, April 2022.
  14. Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno.
    Linear-time recognition of double-threshold graphs.
    Algorithmica 84, 1163-1181, April 2022.
  15. Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi.
    Parameterized complexity of (A, ℓ)-path packing.
    Algorithmica 84, 871-895, April 2022.
  16. Marko Jakovac, Yota Otachi.
    On the security number of the Cartesian product of graphs.
    Discrete Applied Mathematics 304, 119-128, December 2021.
  17. Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi.
    Low-congestion shortcut and graph parameters.
    Distributed Computing 34, 349-365, October 2021.
  18. Masashi Kiyomi, Takashi Horiyama, Yota Otachi.
    Longest common subsequence in sublinear space.
    Information Processing Letters 168, 106084, June 2021.
  19. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, Florian Sikora.
    Token sliding on split graphs.
    Theory of Computing Systems 65, 662-686, May 2021.
  20. Kyohei Chiba, Rémy Belmonte, Hiro Ito, Michael Lampis, Atsuki Nagao, Yota Otachi.
    K3 edge cover problem in a wide sense.
    Journal of Information Processing 28, 849-858, December 2020.
  21. Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Tom van der Zanden.
    Subgraph isomorphism on graph classes that exclude a substructure.
    Algorithmica 82, 3566-3587, December 2020.
  22. Erik D. Demaine, Matias Korman, Jason S. Ku, Joseph S.B. Mitchell, Yota Otachi, André van Renssen, Marcel Roeloffzen, Ryuhei Uehara, Yushi Uno.
    Symmetric assembly puzzles are hard, beyond a few pieces.
    Computational Geometry: Theory and Applications 90, Article 101648, October 2020.
  23. Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, Yota Otachi.
    Independent set reconfiguration parameterized by modular-width.
    Algorithmica 82, 2586-2605, September 2020.
  24. Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, Florian Sikora.
    Parameterized Orientable Deletion.
    Algorithmica 82, 1909-1938, July 2020.
  25. Alessio Conte, Mamadou Moustapha Kanté, Yota Otachi, Takeaki Uno, Kunihiro Wasa.
    Efficient enumeration of maximal k-degenerate induced subgraphs of a chordal graph.
    Theoretical Computer Science 818, 2-11, May 2020.
  26. Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi.
    Parameterized complexity of safe set.
    Journal of Graph Algorithms and Applications 24, 215-245, April 2020.
  27. Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui.
    Space-efficient algorithms for longest increasing subsequence.
    Theory of Computing Systems 64, 522-541, April 2020.
  28. Takumu Shriayama, Takuto Shigemura, Yota Otachi, Shuichi Miyazaki, Ryuhei Uehara.
    On computational complexity of pipe puzzles.
    IEICE Transactions E102-A, 1134-1141, September 2019.
  29. Bireswar Das, Murali Krishna Enduri, Masashi Kiyomi, Neeldhara Misra, Yota Otachi, I. Vinod Reddy, Shunya Yoshimura.
    On structural parameterizations of firefighting.
    Theoretical Computer Science 782, 79-90, August 2019.
  30. Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi, János Pach.
    A lower bound on opaque sets.
    Computational Geometry: Theory and Applications 80, 13-22, July 2019.
  31. Takehiro Ito, Yota Otachi.
    Reconfiguration of colorable sets in classes of perfect graphs.
    Theoretical Computer Science 772, 111-122, June 2019.
  32. Budi Nugroho, Masayoshi Aritsugi, Yota Otachi, Yuki Manabe.
    Combined graph kernels for automatic patent classification: A hybrid approach.
    World Patent Information 57, 18-24, June 2019.
  33. Pavel Klavík, Yota Otachi, Jiří Šejnoha.
    On the classes of interval graphs of limited nesting and count of lengths.
    Algorithmica 81, 1490-1511, April 2019.
  34. Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, Yota Otachi.
    How bad is the freedom to Flood-It?
    Journal of Graph Algorithms and Applications 23, 111-134, January 2019.
  35. Raquel Águeda, Nathann Cohen, Shinya Fujita, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Leandro Montero, Reza Naserasr, Hirotaka Ono, Yota Otachi, Tadashi Sakuma, Zsolt Tuza, Renyu Xu.
    Safe sets in graphs: Graph classes and structural parameters.
    Journal of Combinatorial Optimization 36, 1221-1242, November 2018.
  36. Yixin Cao, Yuping Ke, Yota Otachi, Jie You.
    Vertex deletion problems on chordal graphs.
    Theoretical Computer Science 745, 75-86, October 2018.
  37. Hans L. Bodlaender, Hirotaka Ono, Yota Otachi.
    Degree-constrained orientation of maximum satisfaction: Graph classes and parameterized complexity.
    Algorithmica 80, 2160-2180, July 2018.
  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 729, 1-10, June 2018.
  39. Hans L. Bodlaender, Hirotaka Ono, Yota Otachi.
    A faster parameterized algorithm for Pseudoforest Deletion.
    Discrete Applied Mathematics 236, 42-56, February 2018.
  40. Rémy Belmonte, Yota Otachi, Pascal Schweitzer.
    Induced minor free graphs: Isomorphism and clique-width.
    Algorithmica 80, 29-47, January 2018.
  41. Akira Suzuki, Masashi Kiyomi, Yota Otachi, Kei Uchizawa, Takeaki Uno.
    Hitori numbers.
    Journal of Information Processing 25, 695-707, August 2017.
  42. Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh, Tomás Vyskocil.
    Extending partial representations of interval graphs.
    Algorithmica 78, 945-967, July 2017.
  43. Masashi Kiyomi, Yota Otachi.
    Alliances in graphs of bounded clique-width.
    Discrete Applied Mathematics 223, 91-97, May 2017.
  44. Pavel Klavík, Jan Kratochvíl, Yota Otachi, Ignaz Rutter, Toshiki Saitoh, Maria Saumell, Tomás Vyskocil.
    Extending partial representations of proper and unit interval graphs.
    Algorithmica 77, 1071-1104, April 2017.
  45. Takashi Hayashi, Akitoshi Kawamura, Yota Otachi, Hidehiro Shinohara, Koichi Yamazaki.
    Thin strip graphs.
    Discrete Applied Mathematics 216, 203-210, January 2017.
  46. Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara.
    Ferrers dimension of grid intersection graphs.
    Discrete Applied Mathematics 216, 130-135, January 2017.
  47. Masashi Kiyomi, Yota Otachi.
    Finding a chain graph in a bipartite permutation graph.
    Information Processing Letters 116, 569-573, September 2016.
  48. Matsuo Konagaya, Yota Otachi, Ryuhei Uehara.
    Polynomial-time algorithms for Subgraph Isomorphism in small graph classes of perfect graphs.
    Discrete Applied Mathematics 199, 37-45, January 2016.
  49. Masashi Kiyomi, Yoshio Okamoto, Yota Otachi.
    On the treewidth of toroidal grids.
    Discrete Applied Mathematics 198, 303-306, January 2016.
  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 51, 25-39, January 2016.
  51. Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada.
    Linear-time algorithm for sliding tokens on trees.
    Theoretical Computer Science 600, 132-142, October 2015.
  52. Masayoshi Matsushita, Yota Otachi, Toru Araki.
    Completely independent spanning trees in (partial) k-trees.
    Discussiones Mathematicae Graph Theory 35, 427-437, August 2015.
  53. Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh.
    Extending partial representations of subclasses of chordal graphs.
    Theoretical Computer Science 576, 85-101, April 2015.
  54. Kazuyuki Amano, Kyaw May Oo, Yota Otachi, Ryuhei Uehara.
    Secure sets and defensive alliances in graphs: A faster algorithm and improved bounds.
    IEICE Transactions E98-D, 486-489, March 2015.
  55. Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno.
    Base-object location problems for base-monotone regions.
    Theoretical Computer Science 555, 71-84, October 2014.
  56. Meng Li, Yota Otachi, Takeshi Tokuyama.
    Efficient algorithms for network localization using cores of underlying graphs.
    Theoretical Computer Science 553, 18-26, October 2014.
  57. Takehiro Ito, Shin-ichi Nakano, Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno.
    A 4.31-approximation for the geometric unique coverage problem on unit disks.
    Theoretical Computer Science 544, 14-31, August 2014.
  58. Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, Koichi Yamazaki.
    Approximating the path-distance-width for AT-free graphs and graphs in related classes.
    Discrete Applied Mathematics 168, 69-77, May 2014.
  59. Kyohei Kozawa, Yota Otachi, Koichi Yamazaki.
    Lower bounds for treewidth of product graphs.
    Discrete Applied Mathematics 162, 251-258, January 2014.
  60. Yota Otachi.
    The path-distance-width of hypercubes.
    Discussiones Mathematicae Graph Theory 33, 467-470, May 2013.
  61. Shuji Kijima, Yota Otachi, Toshiki Saitoh, Takeaki Uno.
    Subgraph isomorphism in graph classes.
    Discrete Mathematics 312, 3164-3173, November 2012.
  62. Hans L. Bodlaender, Fedor V. Fomin, Petr A. Golovach, Yota Otachi, Erik Jan van Leeuwen.
    Parameterized complexity of the spanning tree congestion problem.
    Algorithmica 64, 85-111, September 2012.
  63. Katsuhisa Yamanaka, Yota Otachi, Shin-ichi Nakano.
    Efficient enumeration of ordered trees with k leaves.
    Theoretical Computer Science 442, 22-27, July 2012.
  64. Masanobu Ishikawa, Katsuhisa Yamanaka, Yota Otachi, Shin-ichi Nakano.
    Enumerating all rooted trees including k leaves.
    IEICE Transactions E95-D, 763-768, March 2012.
  65. Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, Ryuhei Uehara.
    Random generation and enumeration of bipartite permutation graphs.
    Journal of Discrete Algorithms 10, 84-97, January 2012.
  66. Yoshio Okamoto, Yota Otachi, Ryuhei Uehara.
    On bipartite powers of bigraphs.
    Discrete Mathematics & Theoretical Computer Science 14:2, 11-20, January 2012.
  67. Kyohei Kozawa, Yota Otachi.
    Spanning tree congestion of rook's graphs.
    Discussiones Mathematicae Graph Theory 31, 753-761, November 2011.
  68. Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno.
    Hardness results and an exact exponential algorithm for the spanning tree congestion problem.
    Journal of Graph Algorithms and Applications 15, 727-751, October 2011.
  69. Hans L. Bodlaender, Kyohei Kozawa, Takayoshi Matsushima, Yota Otachi.
    Spanning tree congestion of k-outerplanar graphs.
    Discrete Mathematics 311, 1040-1045, June 2011.
  70. Yota Otachi, Ryohei Suda.
    Bandwidth and pathwidth of three-dimensional grids.
    Discrete Mathematics 311, 881-887, June 2011.
  71. Kyohei Kozawa, Yota Otachi, Koichi Yamazaki.
    The carving-width of generalized hypercubes.
    Discrete Mathematics 310, 2867-2876, November 2010.
  72. Kyohei Kozawa, Yota Otachi, Koichi Yamazaki.
    On spanning tree congestion of graphs.
    Discrete Mathematics 309, 4215-4224, July 2009.
  73. Kyohei Kozawa, Yota Otachi, Koichi Yamazaki.
    Security number of grid-like graphs.
    Discrete Applied Mathematics 157, 2555-2561, June 2009.
  74. Tetsuya Ishizeki, Yota Otachi, Koichi Yamazaki.
    An improved algorithm for longest induced path problem on k-chordal graphs.
    Discrete Applied Mathematics 156, 3057-3059, August 2008.
  75. Yota Otachi, Koichi Yamazaki.
    A lower bound for the vertex boundary-width of complete k-ary trees.
    Discrete Mathematics 308, 2389-2395, June 2008.
  76. Yota Otachi, Yoshio Okamoto, Koichi Yamazaki.
    Relationships between the class of unit grid intersection graphs and other classes of bipartite graphs.
    Discrete Applied Mathematics 155, 2383-2390, October 2007.