Refereed Papers in International Conferences

  1. Yasuaki Kobayashi, Yota Otachi.
    Parameterized complexity of graph burning.
    The 15th International Symposium on Parameterized and Exact Computation (IPEC 2020).
    December 14-18, 2020, in Hong Kong, China (held online). Leibniz International Proceedings in Informatics, to appear.
  2. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi.
    Grundy distinguishes treewidth from pathwidth.
    The 28th European Symposium on Algorithms (ESA 2020).
    September 7-9, 2020, in Pisa, Italy (held online). Leibniz International Proceedings in Informatics 173 (2020) 14:1-14:19.
  3. Taisuke Izumi, Yota Otachi.
    Sublinear-space lexicographic depth-first search for bounded treewidth graphs and planar graphs.
    The 47th International Colloquium on Automata, Languages and Programming (ICALP 2020).
    July 8-11, 2020, in Saarbrücken, Germany (held online). Leibniz International Proceedings in Informatics 168 (2020) 67:1-67:17.
  4. Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Yushi Uno.
    Linear-time recognition of double-threshold graphs.
    The 46th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2020).
    June 24-26, 2020, in Leeds, UK (held online). Lecture Notes in Computer Science, to appear.
  5. 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.
    The 31st International Workshop on Combinatorial Algorithms (IWOCA 2020).
    June 8-10, 2020, in Bordeaux, France (held online). Lecture Notes in Computer Science 12126 (2020) 43-55.
  6. Hans L. Bodlaender, Tesshu Hanaka, Lars Jaffke, Hirotaka Ono, Yota Otachi, Tom C. van der Zanden.
    Hedonic seat arrangement problems (Extended abstract).
    The 19th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS 2020).
    May 9-13, 2020 in Auckland, New Zealand (held online). 1777-1779.
  7. Naoki Kitamura, Hirotaka Kitagawa, Yota Otachi, Taisuke Izumi.
    Low-congestion shortcut and graph parameters.
    The 33rd International Symposium on Distributed Computing (DISC 2019).
    October 14-18, 2019 in Budapest, Hungary. Leibniz International Proceedings in Informatics 146 (2019) 25:1-25:17.
  8. Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, Yota Otachi.
    Independent set reconfiguration parameterized by modular-width.
    The 45th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2019).
    June 19-21, 2019 in Vall de Núria, Catalonia, Spain. Lecture Notes in Computer Science 11789 (2019) 285-297.
  9. Hans L. Bodlaender, Tesshu Hanaka, Yoshio Okamoto, Yota Otachi, Tom van der Zanden.
    Subgraph isomorphism on graph classes that exclude a substructure.
    The 11th International Conference on Algorithms and Complexity (CIAC 2019).
    May 27-29, 2019 in Rome, Italy. Lecture Notes in Computer Science 11485 (2019) 87-98.
  10. Rémy Belmonte, Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Hirotaka Ono, Yota Otachi.
    Parameterized complexity of safe set.
    The 11th International Conference on Algorithms and Complexity (CIAC 2019).
    May 27-29, 2019 in Rome, Italy. Lecture Notes in Computer Science 11485 (2019) 38-49.
  11. Rémy Belmonte, Eun Jung Kim, Michael Lampis, Valia Mitsou, Yota Otachi, Florian Sikora.
    Token sliding on split graphs.
    The 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019).
    March 13-16, 2019 in Berlin, Germany. Leibniz International Proceedings in Informatics 126 (2019) 13:1-13:17.
  12. Tianfeng Feng, Takashi Horiyama, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Takeaki Uno, Ryuhei Uehara.
    Computational complexity of robot arm simulation problems.
    The 29th International Workshop on Combinational Algorithms (IWOCA 2018).
    July 16-19, 2018 in Singapore. Lecture Notes in Computer Science 10979 (2018) 177-188.
  13. Takehiro Ito, Yota Otachi.
    Reconfiguration of colorable sets in classes of perfect graphs.
    The 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018).
    June 18-20, 2018 in Malmö, Sweden. Leibniz International Proceedings in Informatics 101 (2018) 27:1-27:13.
  14. Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, Florian Sikora.
    Parameterized Orientable Deletion.
    The 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018).
    June 18-20, 2018 in Malmö, Sweden. Leibniz International Proceedings in Informatics 101 (2018) 24:1-24:13.
  15. Rémy Belmonte, Mehdi Khosravian Ghadikolaei, Masashi Kiyomi, Michael Lampis, Yota Otachi.
    How bad is the freedom to Flood-It?
    The 9th International Conference on Fun with Algorithms (FUN 2018).
    June 13-15, 2018 in La Maddalena, Italy. Leibniz International Proceedings in Informatics 100 (2018) 5:1-5:13.
  16. Toshihiro Akagi, Tetsuya Araki, Takashi Horiyama, Shin-Ichi Nakano, Yoshio Okamoto, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Takeaki Uno, Kunihiro Wasa.
    Exact algorithms for the max-min dispersion problem.
    The 12th International Frontiers of Algorithmics Workshop (FAW 2018).
    May 8-10, 2018 in Guangzhou, China. Lecture Notes in Computer Science 10823 (2018) 263-272.
  17. Masashi Kiyomi, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui.
    Space-efficient algorithms for longest increasing subsequence.
    The 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018).
    February 28-March 3, 2018 in Caen, France. Leibniz International Proceedings in Informatics 96 (2018) 44:1-44:15.
  18. Yixin Cao, Yuping Ke, Yota Otachi, Jie You.
    Vertex deletion problems on chordal graphs.
    The 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017).
    December 11-15, 2017 in Kanpur, India. Leibniz International Proceedings in Informatics 93 (2018) 22:1-22:14.
  19. Alessio Conte, Mamadou Moustapha Kanté, Yota Otachi, Takeaki Uno, Kunihiro Wasa.
    Efficient enumeration of maximal k-degenerate subgraphs in a chordal graph.
    The 23rd Annual International Computing and Combinatorics Conference (COCOON 2017).
    August 3-5, 2017 in Hong Kong, China. Lecture Notes in Computer Science 10392 (2017) 150-161.
  20. Raquel Águeda, Nathann Cohen, Shinya Fujita, Sylvain Legay, Yannis Manoussakis, Yasuko Matsui, Leandro Montero, Reza Naserasr, Yota Otachi, Tadashi Sakuma, Zsolt Tuza, Renyu Xu.
    Safe sets in graphs: Graph classes and structural parameters.
    The 10th Annual International Conference on Combinatorial Optimization and Applications (COCOA 2016).
    December 16-18, 2016 in Hong Kong, China. Lecture Notes in Computer Science 10043 (2016) 241-253.
  21. Hans L. Bodlaender, Hirotaka Ono, Yota Otachi.
    Degree-constrained orientation of maximum satisfaction: Graph classes and parameterized complexity.
    The 27th International Symposium on Algorithms and Computation (ISAAC 2016).
    December 12-14, 2016 in Sydney, Australia. Leibniz International Proceedings in Informatics 64 (2016) 20:1-20:12.
  22. Pavel Klavík, Yota Otachi, Jiří Šejnoha.
    On the classes of interval graphs of limited nesting and count of lengths.
    The 27th International Symposium on Algorithms and Computation (ISAAC 2016).
    December 12-14, 2016 in Sydney, Australia. Leibniz International Proceedings in Informatics 64 (2016) 45:1-45:13.
  23. Hans L. Bodlaender, Hirotaka Ono, Yota Otachi.
    A faster parameterized algorithm for Pseudoforest Deletion.
    The 11th International Symposium on Parameterized and Exact Computation (IPEC 2016).
    August 24-26, 2016 in Aarhus, Denmark. Leibniz International Proceedings in Informatics 63 (2017) 7:1-7:12.
  24. Akitoshi Kawamura, Sonoko Moriyama, Yota Otachi, János Pach.
    A lower bound on opaque sets.
    The 32nd International Symposium on Computational Geometry (SoCG 2016).
    June 14-18, 2016 in Boston, MA, USA. Leibniz International Proceedings in Informatics 51 (2016) 46:1-46:10.
  25. Eli Fox-Epstein, Duc A. Hoang, Yota Otachi, Ryuhei Uehara.
    Sliding token on bipartite permutation graphs.
    The 26th International Symposium on Algorithms and Computation (ISAAC 2015).
    December 9-11, 2015 in Nagoya, Japan. Lecture Notes in Computer Science 9472 (2015) 237-247.
  26. 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.
    The 18th Japan Conference on Discrete and Computational Geometry and Graphs (JCDCG2 2015).
    September 14-16, 2015 in Kyoto, Japan. Lecture Notes in Computer Science 9943 (2016) 180-192.
  27. Takehiro Ito, Yota Otachi, Toshiki Saitoh, Hisayuki Satoh, Akira Suzuki, Kei Uchizawa, Ryuhei Uehara, Katsuhisa Yamanaka, Xiao Zhou.
    Competitive diffusion on weighted graphs.
    The 14th International Symposium on Algorithms and Data Structures (WADS 2015).
    August 5-7, 2015 in Victoria, BC, Canada. Lecture Notes in Computer Science 9214 (2015) 422-433.
  28. Katsuhisa Yamanaka, Takashi Horiyama, David Kirkpatrick, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara, Yushi Uno.
    Swapping colored tokens on graphs.
    The 14th International Symposium on Algorithms and Data Structures (WADS 2015).
    August 5-7, 2015 in Victoria, BC, Canada. Lecture Notes in Computer Science 9214 (2015) 619-628.
  29. Rémy Belmonte, Yota Otachi, Pascal Schweitzer.
    Induced minor free graphs: Isomorphism and clique-width.
    The 41st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2015).
    June 17-19, 2015 in Munich, Germany. Lecture Notes in Computer Science 9224 (2016) 299-311.
  30. Takehiro Ito, Hirotaka Ono, Yota Otachi.
    Reconfiguration of cliques in a graph.
    The 12th Annual Conference on Theory and Applications of Models of Computation (TAMC 2015).
    May 18-20, 2015 in Singapore. Lecture Notes in Computer Science 9076 (2015) 212-223.
  31. Erik D. Demaine, Martin L. Demaine, Eli Fox-Epstein, Duc A. Hoang, Takehiro Ito, Hirotaka Ono, Yota Otachi, Ryuhei Uehara, Takeshi Yamada.
    Polynomial-time algorithm for sliding tokens on trees.
    The 25th International Symposium on Algorithms and Computation (ISAAC 2014).
    December 15-17, 2014 in Jeonju, Korea. Lecture Notes in Computer Science 8889 (2014) 389-400.
  32. Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, Ryuhei Uehara.
    Depth-first search using O(n) bits.
    The 25th International Symposium on Algorithms and Computation (ISAAC 2014).
    December 15-17, 2014 in Jeonju, Korea. Lecture Notes in Computer Science 8889 (2014) 553-564.
  33. Yota Otachi, Pascal Schweitzer.
    Reduction techniques for graph isomorphism in the context of width parameters.
    The 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014).
    July 2-4, 2014 in Copenhagen, Denmark. Lecture Notes in Computer Science 8503 (2014) 368-379.
  34. 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.
    The 14th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2014).
    July 2-4, 2014 in Copenhagen, Denmark. Lecture Notes in Computer Science 8503 (2014) 253-264.
  35. Steven Chaplick, Pavol Hell, Yota Otachi, Toshiki Saitoh, Ryuhei Uehara.
    Intersection dimension of bipartite graphs.
    The 11th Annual Conference on Theory and Applications of Models of Computation (TAMC 2014).
    April 11-13, 2014, in Chennai, India. Lecture Notes in Computer Science 8402 (2014) 323-340.
  36. Matsuo Konagaya, Yota Otachi, Ryuhei Uehara.
    Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs.
    The 11th Annual Conference on Theory and Applications of Models of Computation (TAMC 2014).
    April 11-13, 2014, in Chennai, India. Lecture Notes in Computer Science 8402 (2014) 216-228.
  37. Yota Otachi, Pascal Schweitzer.
    Isomorphism on subgraph-closed graph classes: a complexity dichotomy and intermediate graph classes.
    The 24th International Symposium on Algorithms and Computation (ISAAC 2013).
    December 16-18, 2013 in Hong Kong, China. Lecture Notes in Computer Science 8283 (2013) 111-118.
  38. Martin Balko, Pavel Klavík, Yota Otachi.
    Bounded representations of interval and proper interval graphs.
    The 24th International Symposium on Algorithms and Computation (ISAAC 2013).
    December 16-18, 2013 in Hong Kong, China. Lecture Notes in Computer Science 8283 (2013) 535-546.
  39. Jinhee Chun, Takashi Horiyama, Takehiro Ito, Natsuda Kaothanthong, Hirotaka Ono, Yota Otachi, Takeshi Tokuyama, Ryuhei Uehara, Takeaki Uno.
    Base location problems for base-monotone regions.
    The 7th International Workshop on Algorithms and Computation (WALCOM 2013).
    February 14-16, 2013 in Kharagpur, India. Lecture Notes in Computer Science 7748 (2013) 53-64.
  40. 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.
    The 23rd International Symposium on Algorithms and Computation (ISAAC 2012).
    December 19-21, 2012 in Taipei, Taiwan. Lecture Notes in Computer Science 7676 (2012) 372-381.
  41. Pavel Klavík, Jan Kratochvíl, Yota Otachi, Toshiki Saitoh.
    Extending partial representations of subclasses of chordal graphs.
    The 23rd International Symposium on Algorithms and Computation (ISAAC 2012).
    December 19-21, 2012 in Taipei, Taiwan. Lecture Notes in Computer Science 7676 (2012) 444-454.
  42. Yota Otachi.
    Isomorphism for graphs of bounded connected-path-distance-width.
    The 23rd International Symposium on Algorithms and Computation (ISAAC 2012).
    December 19-21, 2012 in Taipei, Taiwan. Lecture Notes in Computer Science 7676 (2012) 455-464.
  43. Hiroyuki Fukui, Yota Otachi, Ryuhei Uehara, Takeaki Uno, Yushi Uno.
    On complexity of flooding games on graphs with interval representations.
    Thailand-Japan Joint Conference on Computational Geometry and Graphs (TJJCCGG 2012).
    December 6-8, 2012 in Bangkok, Thailand. Lecture Notes in Computer Science 8296 (2013) 73-84.
  44. 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.
    The 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2012).
    July 4-6, 2012, in Helsinki, Finland. Lecture Notes in Computer Science 7357 (2012) 24-35.
  45. Meng Li, Yota Otachi, Takeshi Tokuyama.
    Efficient algorithms for network localization using cores of underlying graphs.
    The 7th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities (ALGOSENSORS 2011).
    September 8-9, 2011, in Saarbrücken, Germany. Lecture Notes in Computer Science 7111 (2012) 101-114.
  46. Yota Otachi, Toshiki Saitoh, Katsuhisa Yamanaka, Shuji Kijima, Yoshio Okamoto, Hirotaka Ono, Yushi Uno, Koichi Yamazaki.
    Approximability of the path-distance-width for AT-free graphs.
    The 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011).
    June 21-24, 2011, in Teplá, Czech. Lecture Notes in Computer Science 6986 (2011) 271-282.
  47. Yoshio Okamoto, Yota Otachi, Ryuhei Uehara, Takeaki Uno.
    Hardness results and an exact exponential algorithm for the spanning tree congestion problem.
    The 8th Annual Conference on Theory and Applications of Models of Computation (TAMC 2011).
    May 23-25, 2011, in Tokyo, Japan. Lecture Notes in Computer Science 6648 (2011) 452-462.
  48. Yota Otachi, Hans L. Bodlaender, Erik Jan van Leeuwen.
    Complexity results for the spanning tree congestion problem.
    The 36th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2010).
    June 28-30, 2010, in Crete, Greece. Lecture Notes in Computer Science 6410 (2010) 3-14.
  49. Toshiki Saitoh, Yota Otachi, Katsuhisa Yamanaka, Ryuhei Uehara.
    Random generation and enumeration of bipartite permutation graphs.
    The 20th International Symposium on Algorithms and Computation (ISAAC 2009).
    December 16-18, 2009 in Hawaii, USA. Lecture Notes in Computer Science 5878 (2009) 1104-1113.
  50. Katsuhisa Yamanaka, Yota Otachi, Shin-ichi Nakano.
    Efficient enumeration of ordered trees with k leaves.
    The 3rd Annual Workshop on Algorithms and Computation (WALCOM 2009).
    February 18-20, 2009 in Kolkata, India. Lecture Notes in Computer Science 5431 (2009) 141-150.