My page was moved to yasu0207.github.io/ .


Yasuaki Kobayashi

Graduate School of Informatics, Kyoto University

Journal Paper

  • Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Daniel, Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, Uéverton S. Souza: Computing the Largest Bond and the Maximum Connected Cut of a Graph. Accepted, Algorithmica, 2020. [arXiv]

  • Hans L. Bodlaender, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Yoshio Okamoto, Yota Otachi, Tom C. van der Zanden: Subgraph Isomorphism on Graph Classes that Exclude a Substructure. Algorithmica 82(12), 3566-3587, 2020. [arXiv]

  • Yasuaki Kobayashi, Hisao Tamaki: A faster fixed parameter algorithm for two-layer crossing minimization, Information Processing Letters 116(9), 547-549, 2016. [Arxiv]

  • Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, Toshihiro Tano: Computing directed pathwidth in O(1.89n) time, Algorithmica, 75(1), 138-157, 2016.

  • Yasuaki Kobayashi, Hisao Tamaki: A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization. Algorithmica 72(3), 778-790, 2015.

  • Yasuaki Kobayashi: Computing the pathwidth of directed graphs with small vertex cover. Information Processing Letters 115(2), 310-312, 2015.

  • Yasuaki Kobayashi, Hirokazu Maruta, Yusuke Nakae Hisao Tamaki: A linear edge kernel for two-layer crossing minimization. Theoretical Computer Science 554, 74-81, 2014.

Conference Paper

  • Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi: Finding Diverse Trees, Paths, and More. Accepted, AAAI 2021, 2021. [arXiv]

  • Yasuaki Kobayashi, Yota Otachi: Parameterized Complexity of Graph Burning. In Proc. of IPEC 2020, LIPICS, vol. 180, 21:1-21:10, 2020. [arXiv]

  • Kazuhiro Kurita, Yasuaki Kobayashi: Efficient Enumerations for Minimal Multicuts and Multiway Cuts. Proc of MFCS 2020, ILPICS vol. 170, 60:1--60:14, 2020. [arXiv]

  • Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono and Yota Otachi: Parameterized Complexity of (A,l)-Path Packing. In Proc of IWOCA 2020, LNCS vol. 12126, pp. 43-55, 2020. [arXiv]

  • Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone: An optimal algorithm for bisection for bounded-treewidth graphs. Proc. of FAW 2020, LNCS, vol. 12340, 25-36, 2020.

    • A slightly improved version is available on arXiv.: A (probably) optimal algorithm for Bisection on bounded-treewidth graphs. 2020. [arXiv]

  • Hikaru Shindo, Masaaki Nishino, Yasuaki Kobayashi, Akihiro Yamamoto: Metric Learning for Ordered Labeled Trees with pq-grams. Proceedings of ECAI 2020, 1475-1482, 2020. [arXiv] [code]

  • Yasuaki Kobayashi, Kensuke Kojima, Norihide Matsubara, Taiga Sone, Akihiro Yamamoto: Algorithms and hardness results for the maximum balanced connected subgraph problem. In Proc of COCOA 2019, LNCS vol. 11949, pp. 303-315, 2019. [arXiv]

  • Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki, Ryuhei Uehara: On the complexity of lattice puzzles. In Proc of ISAAC 2019, LIPICS, vol. 149, 32:1-32:12, 2019.

  • Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi: Parameterized Algorithms for Maximum Cut with Connectivity Constraints, In Proc of IPEC 2019, LIPICS, vol. 148, 13:1-13:15, 2019. [arXiv]

  • Yasuaki Kobayashi, Yusuke Kobayashi, Shuichi Miyazaki, Suguru Tamaki: An improved fixed-parameter algorithm for max-cut parameterized by crossing number. In Proc of IWOCA 2019, LNCS, vol. 11638, 327-338, 2019. [arXiv] Best Paper Award

  • Yusuke Shido, Yasuaki Kobayashi, Akihiro Yamamoto, Atsushi Miyamoto, Tadayuki Matsumura: Automatic source code summarization with extended tree-LSTM. Accepted, IJCNN 2019, 2019. [arXiv] [code]

  • Eunpyeong Hong, Yasuaki Kobayashi, Akihiro Yamamoto: Improved Methods for Computing Distances between Unordered Trees Using Integer Programming. In Proc. of COCOA 2017, LNCS, vol. 10628, pp. 45-60, 2017. [arXiv] [code]

  • Yasuaki Kobayashi, Hiromu Ohtsuka, Hisao Tamaki: An improved fixed-parameter algorithm for one-page crossing minimization, IPEC 2017, accepted, 2017.

  • Yasuaki Kobayashi, Hisao Tamaki: Treedepth parameterized by vertex cover number, In Proc. of IPEC, LIPICS, vol. 63, 18:1-18:11, 2016.

  • Kenta Kitsunai, Yasuaki Kobayashi, Hisao Tamaki: On the pathwidth of almost semicomplete digraphs, In Proc. of ESA, LNCS, vol. 9294, pp.816-827, 2015. [Arxiv]

  • Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki: Search space reduction through commitments in pathwidth computation: an experimental study. In Proc. of SEA2014, LNCS, vol. 8504, pp. 388-399, 2014.

  • Yasuaki Kobayashi, Hirokazu Maruta, Yusuke Nakae, Hisao Tamaki: A linear edge kernel for two-layer crossing minimization. In Proc. of COCOON2013, LNCS, vol. 7936, pp. 458-468, 2013.

  • Yasuaki Kobayashi, Hisao Tamaki: A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization. In Proc. of ESA2012, LNCS, vol. 7501, pp.683-694, 2012.

  • Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, Toshihiro Tano: Computing directed pathwidth in O(1.89n) time. In Proc. of IPEC2012, LNCS, vol. 7535, pp. 182-193, 2012.

  • Yasuaki Kobayashi, Yuichiro Miyamoto, Hisao Tamaki: k-cyclic orientations of graphs. In Proc. of ISAAC2010, LNCS, vol. 6507(2), pp.73-84, 2010.