Yasuaki Kobayashi
Home
Research
その他

Journal Papers

  1. Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono, Yota Otachi: Structural Parameterizations of Vertex Integrity. Theoretical Computer Science, accepted, 2024. (doi) (arXiv)

  2. Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa: Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints. Discrete Applied Mathematics, 361(30), 258-275, 2025. (doi) (arXiv)

  3. Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi: Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited. Algorithmica, 86, 3395-3424, 2024. (doi) (arXiv)

  4. Yuuki Aoike, Masashi Kiyomi, Yasuaki Kobayashi, Yota Otachi: Finding a reconfiguration sequence between longest increasing subsequences. IEICE TRANSACTIONS on Information and Systems, vol. E107.D(4), 559-563, 2024. (doi) (arXiv)

  5. Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa: Reconfiguring (non-spanning) arborescences. Theoretical Computer Science, 943, 131-141, 2023. (doi) (arXiv)

  6. 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, 2022. (doi) (arXiv)

  7. Yasuaki Kobayashi, Yota Otachi: Parameterized Complexity of Graph Burning. Algorithmica, 84(8), 2379-2393, 2022. (doi) (arXiv)

  8. 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, 2022. (doi) (arXiv)

  9. Yasuaki Kobayashi, Shin-Ichi Nakano, Kei Uchizawa, Takeaki Uno, Yutaro Yamaguchi, Katsuhisa Yamanaka: An \(O(n^2)\)-Time Algorithm for Computing a Max-Min 3-Dispersion on a Point Set in Convex Position. IEICE TRANSACTIONS on Information and Systems, E105-D(3), 503-507, 2022. (doi)

  10. Rémy Belmonte, Tesshu Hanaka, Masaaki Kanzaki, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Michael Lampis, Hirotaka Ono, Yota Otachi: Parameterized Complexity of \((A,\ell)\)-Path Packing. Algorithmica, 84(4), 871-895, 2022. (doi) (arXiv)

  11. Tesshu Hanaka, Yasuaki Kobayashi, Taiga Sone: A (probably) optimal algorithm for Bisection on bounded-treewidth graphs. Theoretical Computer Science 873, 38-46, 2021. (doi) (arXiv)

  12. Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Tsuyoshi Yagita: Finding a Maximum Minimal Separator: Graph Classes and Fixed-Parameter Tractability. Theoretical Computer Science 865, 131-140, 2021. (doi) (arXiv)

  13. 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. Algorithmica, 83(5), 1421-1458, 2021. (doi) (arXiv)

  14. 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. (doi) (arXiv)

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

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

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

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

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

Conference Papers

  1. Tesshu Hanaka, Yuni Iwamasa, Yasuaki Kobayashi, Yuto Okada, Rin Saito: Basis sequence reconfiguration in the union of matroids. ISAAC 2024, accepted, 2024. (arXiv)

  2. Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Hirotaka Ono: Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints. IWOCA 2024, LNCS, vol. 14764, pp. 232-246, 2024. (doi) (arXiv)

  3. Yuto Shida, Giulia Punzi, Yasuaki Kobayashi, Takeaki Uno, Hiroki Arimura: Finding Diverse Strings and Longest Common Subsequences in a Graph. CPM 2024, LIPIcs, vol. 296, pp. 27:1-27:19, 2024. (doi) (arXiv)

  4. Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono, Kazuhisa Seto, Ryu Suzuki: Theoretical Aspects of Generating Instances with Unique Solutions: Pre-assignment Models for Unique Vertex Cover. AAAI 2024, 38(18), 20726-20734, 2024. (doi) (arXiv)

  5. Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Yota Otachi, Tomohito Shirai, Akira Suzuki, Yuma Tamura, Xiao Zhou: On the Complexity of List \(\mathcal H\)-Packing for Sparse Graph Classes. WALCOM 2024, LNCS, vol. 14549, pp. 421-435, 2024. (doi) (arXiv)

  6. Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Ryota Murai, Hirotaka Ono, Yota Otachi: Structural Parameterizations of Vertex Integrity. WALCOM 2024, LNCS, vol. 14549, pp. 406-420, 2024. (doi) (arXiv) Best Paper Award

  7. Hiroki Arimura, Shunsuke Inenaga, Yasuaki Kobayashi, Yuto Nakashima, Mizuki Sue: Optimally Computing Compressed Indexing Arrays Based on the Compact Directed Acyclic Word Graph. SPIRE 2023, LNCS, vol.12240, pp. 28-34, 2023. (doi) (arXiv)

  8. Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa: Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids. MFCS 2023, LIPIcs, vol. 272, 58:1-58:14, 2023. (doi) (arXiv)

  9. Takehiro Ito, Yuni Iwamasa, Naoyuki Kamiyama, Yasuaki Kobayashi, Yusuke Kobayashi, Shun-ichi Maezawa, Akira Suzuki: Reconfiguration of Time-Respecting Arborescences. In Proceedings of WADS 2023, LNCS, vol. 14079, pp. 521-532, 2023. (doi) (arXiv)

  10. Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi, Yusuke Kobayashi, Kazuhiro Kurita, Yota Otachi: A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems. In Proceedings of AAAI 2023, 37(4), 3968-3976, 2023. (doi) (arXiv)

  11. Ankit Abhinav, Susobhan Bandopadhyay, Aritra Banik, Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi, Saket Saurabh: Parameterized Complexity of Non-Separating and Non-Disconnecting Paths and Sets. In Proceedings of MFCS 2022, LIPIcs, vol. 241, 6:1-6:15, 2022. (doi) (arXiv)

  12. Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Masahiro Takahashi, Kunihiro Wasa: Independent set reconfiguration on directed graphs. In Proceedings of MFCS 2022, LIPIcs, vol. 241, 58:1-58:15, 2022. (doi) (arXiv)

  13. Tatsuya Gima, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi: Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited. ESA 2022, LIPIcs, vol. 244, 61:1-61:15, 2022. (doi) (arXiv)

  14. Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa: Polynomial-Delay and Polynomial-Space Enumeration of Large Maximal Matchings. WG 2022, LNCS vol. 13453, pp. 342-355, 2022. (doi) (arXiv)

  15. Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, Yota Otachi: Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study. AAAI 2022, 36(4), 3758-3766, 2022. (oral presentation) (doi) (arXiv) (code)

  16. Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, Kunihiro Wasa: Reconfiguration of Regular Induced Subgraphs. WALCOM 2022, LNCS, vol. 13174, pp. 35-46, 2022. (doi) (arXiv)

  17. Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa: Linear-Delay Enumeration for Minimal Steiner Problems. In Proc. of PODS 2022, pp. 301–313, 2022. (doi) (arXiv)

  18. Yasuaki Kobayashi: On Structural Parameterizations of Node Kayles. In Proc. of JCDCGGG 2018, LNCS, vol. 13034, pp. 96-105, 2021. (doi) (arXiv)

  19. Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa: Reconfiguring Directed Trees in a Digraph. In Proc. of COCOON 2021, LNCS, vol. 13025, pp. 343-354, 2021. (doi) (arXiv)

  20. Tatsuya Gima, Tesshu Hanaka, Masashi Kiyomi, Yasuaki Kobayashi and Yota Otachi: Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity. In Proc. of CIAC 2021, LNCS, vol. 12701, pp. 271-285, 2021. (doi) (arXiv)

  21. Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, Yota Otachi: Finding Diverse Trees, Paths, and More. In Proc. of AAAI 2021, 35(5), 3778-3786, 2021. (doi) (arXiv)

  22. Yasuaki Kobayashi, Yota Otachi: Parameterized Complexity of Graph Burning. In Proc. of IPEC 2020, LIPICS, vol. 180, 21:1-21:10, 2020. (doi) (arXiv)

  23. Kazuhiro Kurita, Yasuaki Kobayashi: Efficient Enumerations for Minimal Multicuts and Multiway Cuts. In Proc of MFCS 2020, LIPICS vol. 170, 60:1–60:14, 2020. (doi) (arXiv)

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

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

  26. Hikaru Shindo, Masaaki Nishino, Yasuaki Kobayashi, Akihiro Yamamoto: Metric Learning for Ordered Labeled Trees with \(pq\)-grams. In Proc. of ECAI 2020, 1475-1482, 2020. (doi) (arXiv) (code)

  27. 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. (doi) (arXiv)

  28. 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. (doi)

  29. 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. (doi) (arXiv)

  30. 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.(doi) (arXiv) Best Paper Award

  31. Yusuke Shido, Yasuaki Kobayashi, Akihiro Yamamoto, Atsushi Miyamoto, Tadayuki Matsumura: Automatic source code summarization with extended tree-LSTM. Proceedings of IJCNN 2019, 2019. (doi) (arXiv) (code)

  32. 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. (doi) (arXiv) (code)

  33. Yasuaki Kobayashi, Hiromu Ohtsuka, Hisao Tamaki: An improved fixed-parameter algorithm for one-page crossing minimization. In Proc. of IPEC 2017, LIPICS, vol. 89, 25:1-25:12, 2017. (doi)

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

  35. Kenta Kitsunai, Yasuaki Kobayashi, Hisao Tamaki: On the pathwidth of almost semicomplete digraphs. In Proc. of ESA 2015, LNCS, vol. 9294, pp.816-827, 2015. (doi) (arXiv)

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

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

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

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

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

Other Conferences

  1. Kazuhiro Kurita, Yasuaki Kobayashi, Kunihiro Wasa: Polynomial-Delay and Polynomial-Space Enumeration of Heavy Maximal Matchings. WEPA 2024, Tochigi, 2024.

  2. Alessio Conte, Roberto Grossi, Yasuaki Kobayashi, Kazuhiro Kurita, Davide Rucci, Takeaki Uno, Kunihiro Wasa: Amortized Enumeration of Graphlets. WEPA 2024, Tochigi, 2024.

  3. Yudai Egami, Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi and Yota Otachi: FPT Approximation Algorithms for Telephone Broadcasting Parameterized by Clique Cover Number. WAAC 2024, Seoul, 2024.

  4. Ryu Suzuki, Yasuaki Kobayashi, Kazuhisa Seto and Takashi Horiyama: NP-completeness of Computing Pre-assignments to Uniquify Vertex Cover for Bipartite Graphs. WAAC 2023, Nagoya, 2023.

  5. Hiroki Arimura, Tatsuya Gima, Yasuaki Kobayashi, Hiroomi Nochide, Yota Otachi: Minimum Consistent Subset for Trees Revisited. WAAC 2023, Nagoya, 2023.

  6. Ryota Murai, Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Hirotaka Ono and Yota Otachi: Structural Parameterizations of Vertex Integrity. WAAC 2023, Nagoya, 2023.

  7. Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa: Polynomial-Delay Enumeration of Large Maximal Matchings. WEPA 2022, Clermont-Ferrand, 2022.

  8. Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Yota Otachi, Kunihiro Wasa: Reconfiguring Directed Trees in a Digraph. Combinatorial Reconfiguration, Satellite workshop of ICALP 2021, Online, 2021.

  9. Yasuaki Kobayashi, Shin-Ichi Nakano, Kei Uchizawa, Takeaki Uno, Yutaro Yamaguchi, Katsuhisa Yamanaka: Max-Min 3-dispersion on a Convex Polygon. EuroCG 2021, Online, 2021.

  10. Kazuhiro Kurita, Yasuaki Kobayashi and Kunihiro Wasa: Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Cardinality Constraints. WEPA 2020, Online, 2020.

  11. Yasuaki Kobayashi, Koki Suetsugu, Hideki Tsuiki: On the complexity of lattice puzzles. JCDCGGG 2017, Tokyo, Japan, 2017.

Preprints (unpublished)

  • Alessio Conte, Roberto Grossi, Yasuaki Kobayashi, Kazuhiro Kurita, Davide Rucci, Takeaki Uno, Kunihiro Wasa: Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size. 2024 (arXiv)

  • Ryo Funayama, Yasuaki Kobayashi, Takeaki Uno: Parameterized Complexity of Finding Dissimilar Shortest Paths. 2024. (arXiv)

  • Tesshu Hanaka, Yasuaki Kobayashi: Finding a Minimum Spanning Tree with a Small Non-Terminal Set. 2023. (arXiv)

  • Hiroki Arimura, Tatsuya Gima, Yasuaki Kobayashi, Hiroomi Nochide, Yota Otachi: Minimum Consistent Subset for Trees Revisited. 2023. (arXiv)

  • Yasuaki Kobayashi, Yu Nakahata: A Note on Exponential-Time Algorithms for Linearwidth. 2020. (arXiv)

  • 小林靖明: グラフのカット幅を求める高速な厳密アルゴリズムの開発, 学習院大学計算機センター年報，Vol. 37，90 - 100，2016．

Software

  1. Diverse Shortest Paths (AAAI 2022) (link)

  2. Metric Learning for Ordered Trees with pq-grams (ECAI 2020) (link)

  3. Automatic Source Code Summarization with Extended Tree-LSTM (IJCNN 2019) (link)

  4. Minimum Steiner Tree Solver on Tree Decomposition (PACE 2018) (link)

  5. Minimum Fill-In Solver (PACE 2017) (link)

  6. ILP formulation for unordered tree edit distance (COCOA 2017) (link)

講演

  1. 疎グラフに対するアルゴリズム的メタ定理 日本OR学会 RAMP数理最適化シンポジウム 2021

  2. 単調な性質を持つサイズ制約付き極小解の近似列挙アルゴリズム 日本OR学会 超スマート社会のシステムデザインのための理論と応用研究部会 2020

  3. SATソルバを用いた問題解決法 京都大学国際高等教育院データ科学イノベーション教育研究センター データサイエンススプリングスクール 2019

  4. 木幅と動的計画法 京都大学学術情報メディアセンターセミナー「グラフアルゴリズムの進展」2018

国内研究会・会議等

  1. 土中哲秀，岩政勇仁，小林靖明，岡田優斗，斉藤凛：マトロイドの基の組の遷移問題．．電子情報通信学会 コンピュテーション研究会，宮城，2024.

  2. 藤原優，儀間達也，小林靖明：辺カット型グラフパラメータに基づく最大出次数最小化問題と標的集合選択問題の計算複雑性．情報処理学会 第199回アルゴリズム研究会，広島，2024．

  3. Takashi Horiyama, Yasuaki Kobayashi, Hirotaka Ono, Kazuhisa Seto, Ryu Suzuki: Exact Algorithms for Uniquify Minimum Vertex Covers under Pre-assignment Models. 電子情報通信学会 コンピュテーション研究会，京都，2024.

  4. 儀間達也，岩政勇仁，小林靖明，栗田和宏，大舘陽太，斉藤凛：Computing diverse pair of solutions for SAT. 電子情報通信学会総合大会 COMP-AFSA学生シンポジウム，広島，2024．

  5. 堀山貴史，小林靖明，小野廣隆，脊戸和寿，鈴木琉：Hardness of Uniquifying Minimum Vertex Covers and Minimum Dominating Sets under Pre-assignments. 電子情報通信学会総合大会 COMP-AFSA学生シンポジウム，広島，2024．

  6. 儀間達也，岩政勇仁，小林靖明，栗田和宏，大舘陽太，斉藤凛：Computing diverse pair of solutions for SAT. 2023年冬のLAシンポジウム，京都，2024．

  7. 小林靖明，栗田和宏：極小シュタイナー多点対頂点カット列挙の計算困難性．2023年冬のLAシンポジウム，京都，2024．

  8. Tatsuya Gima, Tesshu Hanaka, Yasuaki Kobayashi, Yota Otachi, Tomohito Shirai, Akira Suzuki, Yuma Tamura, Xiao Zhou: List Variants of Packing Problems on Sparse Graphs. 情報処理学会 第196回アルゴリズム研究会，東京，2024．

  9. 志田祐仁，小林靖明，有村博紀: 文字列集合に対する多様な最長共通部分列の発見. 電子情報通信学会 コンピュテーション研究会，宮崎，2023.

  10. 佐藤嶺，小林靖明，栗田和宏，和佐州洋: 弦グラフの部分クラスにおける極大誘導部分グラフ列挙への多項式遅延アルゴリズム. 電子情報通信学会 コンピュテーション研究会，宮崎，2023.

  11. 舟山諒，小林靖明: 多様な最短経路を求める固定パラメータアルゴリズム. 電子情報通信学会 コンピュテーション研究会，宮崎，2023.

  12. 小林靖明，栗田和宏: 要素数制約付き極小辺被覆の多項式遅延列挙. 人工知能学会 第126回人工知能基本問題研究会, 神奈川，2023.

  13. 藤原優，吉岡和希，小林靖明: 連結制約のある頂点符号付きグラフ分割問題の緩和問題に対する高速なアルゴリズム. 人工知能学会 第126回人工知能基本問題研究会, 神奈川，2023.

  14. 小林靖明，栗田和宏，和佐州洋: 要素数制約付き極大マトロイド共通独立集合の多項式遅延列挙. 日本オペレーションズ・リサーチ学会 2023年秋季研究発表会＆シンポジウム, 兵庫，2023．

  15. Yasuaki Kobayashi, Kazuhiro Kurita, Yasuko Matsui, Hirotaka Ono: Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints. 電子情報通信学会 コンピュテーション研究会，大阪，2023.

  16. 舟山諒，小林靖明: 多様な最短経路を求める固定パラメータアルゴリズム. 2023年夏のLAシンポジウム，函館，2023.

  17. 伊藤健洋，岩政勇仁，神山直之，小林靖明，小林佑輔，前澤俊一，鈴木顕: 時間制約付き有向木の遷移. 2023年夏のLAシンポジウム，函館，2023.

  18. Ryu Suzuki, Yasuaki Kobayashi, Kazuhisa Seto, Takashi Horiyama: NP-completeness of Computing Pre-assignments to Uniquify Vertex Cover for Bipartite Graphs. 2023年夏のLAシンポジウム，函館，2023.

  19. Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita: Maximum Minimal \(k\)-Path Vertex Cover Problem. 情報処理学会 第192回アルゴリズム研究会，宮城，2023．

  20. 村井亮太，儀間達也，土中哲秀，小林靖明，小野廣隆，大舘陽太: 頂点インテグリティのパラメータ化計算量．2022年冬のLAシンポジウム，京都，2023．

  21. 儀間達也，伊藤健洋，小林靖明，大舘陽太: Algorithmic meta-theorems for combinatorial reconfiguration revisited．2022年冬のLAシンポジウム，京都，2023．

  22. 伊藤大修，山中克久，平山貴司，小林靖明: Reconfiguration of Linear Extensions．情報処理学会 第191回アルゴリズム研究会，福岡，2023．

  23. 須江瑞樹，小林靖明，有村博紀，中島祐人，稲永俊介: コンパクト非巡回語グラフに基づく連長圧縮Burrows–Wheeler変換の効率良い構築．電子情報通信学会 コンピュテーション研究会，愛媛，2022.

  24. 宮﨑玲子，有村博紀，小林靖明: 半順序集合の弱埋め込み問題に対するパラメータ化アルゴリズム．電子情報通信学会 コンピュテーション研究会，愛媛，2022.

  25. Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa: Efficient Enumeration of Spanning Subgraphs in Planar Graphs with Edge Connectivity Constraints. 電子情報通信学会 コンピュテーション研究会，福岡，2022.

  26. 江藤宏，伊藤健洋，小林靖明，大舘陽太，和佐州洋: 正則誘導部分グラフ遷移問題の計算複雑さ．日本オペレーションズ・リサーチ学会 2022年秋季研究発表会＆シンポジウム， 新潟，2022．

  27. 江藤宏，伊藤健洋，小林靖明，前澤俊一，大舘陽太，和佐州洋: 木における誘導マッチング遷移．Japanese Conference on Combinatorics and Its Applications 2022, 東京+オンライン，2022．

  28. 儀間達也，伊藤健洋，小林靖明，大舘陽太: Algorithmic meta-theorems for combinatorial reconfiguration revisited．Japanese Conference on Combinatorics and Its Applications 2022，東京+オンライン，2022．

  29. 儀間達也，伊藤健洋，小林靖明，大舘陽太: Algorithmic meta-theorems for combinatorial reconfiguration revisited．最適化手法とアルゴリズム (SOMA) ─未来を担う若手研究者の集い 2022─, 東京+オンライン，2022.

  30. Yasuaki Kobayashi, Shunsuke Nagano, Yota Otachi: Finding shortest non-separating and non-disconnecting paths. 情報処理学会 第187回アルゴリズム研究会，東京+オンライン，2022．

  31. 青池宥希，清見礼，小林靖明，大舘陽太: 置換グラフ上の最大独立集合遷移問題の多項式時間解法．2021年度「組合せ遷移」の学生シンポジウム，オンライン，2022．

  32. 伊藤大修，山中克久，平山貴司，小林靖明: 線形拡張の遷移問題に関する研究．2021年度「組合せ遷移」の学生シンポジウム，オンライン，2022．

  33. Tesshu Hanaka, Yasuaki Kobayashi: Fixed-parameter tractability of linear extension diameter. 電子情報通信学会 コンピュテーション研究会，オンライン，2022.

  34. 栗田和宏，土中哲秀，清見礼，小林靖明，小林佑輔，大舘陽太: 多様な解集合を発見する効率良い近似アルゴリズム．人工知能学会 第119回人工知能基本問題研究会，オンライン，2022．

  35. Hiroshi Eto, Takehiro Ito, Yasuaki Kobayashi, Yota Otachi, Kunihiro Wasa: Complexity of reconfiguration of regular induced subgraphs. 電子情報通信学会 コンピュテーション研究会，石川+オンライン，2021.

  36. Takehiro Ito, Yuni Iwamasa, Yasuaki Kobayashi, Yu Nakahata, Masahiro Takahashi, Yota Otachi, Kunihiro Wasa: Token Sliding on Directed Graphs. 電子情報通信学会 コンピュテーション研究会，石川+オンライン，2021.

  37. 小林靖明，栗田和宏: 省メモリなトップK列挙アルゴリズムの設計技法．人工知能学会 第117回人工知能基本問題研究会，オンライン，2021．

  38. 小林靖明，小林佑輔，大舘陽太: カテゴリカル変数の背後にある構造を利用した決定木学習の困難さ．人工知能学会 第117回人工知能基本問題研究会，オンライン，2021．

  39. 青池宥希，清見礼，小林靖明，大舘 陽太: 区間順序上の最長増加部分列．情報処理学会 第184回アルゴリズム研究会，オンライン，2021．

  40. 小林靖明，栗田和宏: マトロイドマッチングとマトロイド交叉上の独立集合に対する効率良い列挙．2021年夏のLAシンポジウム，オンライン，2021．

  41. 栗田和宏，小林靖明，和佐州洋: 大きな極大マッチングの多項式遅延列挙．人工知能学会　第35回人工知能学会全国大会 JSAI2021，オンライン，2021．

  42. Tesshu Hanaka, Yasuaki Kobayashi, Kazuhiro Kurita, See Woo Lee, Yota Otachi: On Tractable Problems of Diversity Optimization. 情報処理学会 第183回アルゴリズム研究会，オンライン，2021．

  43. 小林靖明，中野眞一，内澤啓，宇野毅明，山口勇太郎，山中克久: Max-Min 3-dispersion on a Convex Polygon. 情報処理学会 第183回アルゴリズム研究会，オンライン，2021．

  44. 吉村仁志，小林靖明，山本章博: 順列グラフのカラフル独立集合問題に対するアルゴリズム．情報処理学会 第182回アルゴリズム研究会，オンライン，2021．

  45. 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. 電子情報通信学会 コンピュテーション研究会，オンライン，2020.

  46. Yasuaki Kobayashi, Kazuhiro Kurita, Kunihiro Wasa: Polynomial delay enumeration for Steiner problems. 電子情報通信学会 コンピュテーション研究会，大阪&オンライン，2020．

  47. 土中哲秀，小林靖明，栗田和宏，大舘陽太: 多様な部分グラフを発見するアルゴリズム．第113回人工知能基本問題研究会，オンライン，2020．2020年度人工知能学会研究会優秀賞

  48. 久保田稜，小島健介，小林靖明，山本章博: 可換マッチング問題の固定パラメーター容易性に関する研究．人工知能学会，第113回人工知能基本問題研究会 (振替)，オンライン，2020

  49. 小林靖明: ピッチャーを空にできるか？ 第4回日本組合せゲーム理論研究集会，オンライン，2020．

  50. 栗田和宏，小林靖明: Efficient enumeration of minimal multiway cuts. 情報処理学会 第177回アルゴリズム研究会 (振替)，オンライン，2020．

  51. 小林靖明，小島健介，曽根大雅，松原徳秀，山本章博: 最大平衡連結部分グラフに対するアルゴリズム．数理離散情報研究会 (定山渓セミナー)，札幌，2020．

  52. 栗田和宏，小林靖明: グラフの極小多分割カットの効率よい列挙．2019年度冬のLAシンポジウム，京都，2020．

  53. Rémy Belmonte，土中哲秀，神崎勝彰，清見礼，小林靖明，小林佑輔，Michael Lampis，小野廣隆，大舘陽太: Packing disjoint \(A\)-paths with fixed length．2019年度冬のLAシンポジウム，京都，2020．

  54. 儀間達也，土中哲秀，清見礼，小林靖明，大舘陽太: Graph partitioning problems parameterized by vertex integrity．2019年度冬のLAシンポジウム，京都，2020．

  55. 小林靖明: グラフ上のTron．第31回列挙アルゴリズムセミナー，群馬，2020．

  56. 小林靖明，曽根大雅，土中哲秀: グラフの2等分割問題に対するアルゴリズムと計算複雑性．情報処理学会 第175回アルゴリズム研究会，福岡，2019

  57. 小林靖明，曽根大雅，土中哲秀: グラフの最適2等分割問題に対するアルゴリズムと困難性．基盤(S)離散構造処理系プロジェクト「2019年度 秋のワークショップ」，北海道，2019．

  58. Yasuaki Kobayashi, Kensuke Kojima, Norihide Matsubara, Taiga Sone, Akihiro Yamamoto: Algorithms and hardness results for the maximum balanced connected subgraph problem. 電子情報通信学会 コンピュテーション研究会，北海道，2019.

  59. 新藤光，西野正彬，小林靖明，山本章博: pq-gramを用いた木構造間の距離の学習．人工知能学会，第110回人工知能基本問題研究会，北海道，2019．

  60. 小林靖明，中畑裕: 線形枝幅を計算する厳密アルゴリズムとフロンティア法への応用．人工知能学会，第110回人工知能基本問題研究会，北海道，2019．

  61. 小林靖明，小林佑輔，宮崎修一，玉置卓: 少ない交差で描画できるグラフ上の最大カット問題．Japanese Conference on Combinatorics and Its Applications 2019，宮崎，2019．

  62. 江藤宏，土中哲秀，小林靖明，小林佑輔: 最大連結カットに対するパラメータアルゴリズム．2019年夏のLAシンポジウム，愛知，2019．

  63. 久保田稜，小島健介，小林靖明，山本章博: 可換な単一化の固定パラメーター容易性の検討，2019年夏のLAシンポジウム，愛知，2019．

  64. 松田浩幸，紫藤佑介，小林靖明，山本章博，宮本篤志，松村忠幸: コンテキストと構文の情報を用いたニューラルネットによる変数名予測．情報処理学会研究報告．第202回ソフトウェア工学研究発表会，北海道，2019．

  65. 小林靖明，曽根大雅，松原徳秀，山本章博: 最大Balanced Connected Subgraphに対するアルゴリズム．基盤(S)離散構造処理系プロジェクト「2019年度 初夏のワークショップ」，北海道，2019．

  66. 小林靖明: フロンティア法による半順序集合の線形拡張の列挙．基盤(S)離散構造処理系プロジェクト「2019年度 初夏のワークショップ」，北海道，2019．

  67. 新藤光，小林靖明，山本章博: p,q-gramを用いた木構造間の距離の学習の検討．基盤(S)離散構造処理系プロジェクト「2019年度 初夏のワークショップ」，北海道，2019．

  68. 小林靖明，末續鴻輝，立木秀樹 ，上原隆平: 格子パズルの困難性と多項式時間アルゴリズムの研究．電子情報通信学会 コンピュテーション研究会，熊本，2019．

  69. 小林靖明: 半順序集合の次元を求める固定パラメータアルゴリズム．電子情報通信学会 コンピュテーション研究会，熊本，2019．

  70. 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. 電子情報通信学会 コンピュテーション研究会，熊本，2019.

  71. 小林靖明: パンケーキについて．第30回列挙アルゴリズムセミナー，群馬，2019．

  72. 里見琢聞，小林靖明，山本章博: 文字列データの線形最小汎化問題に対するアルゴリズム ，人工知能学会，第109回人工知能基本問題研究会，長崎，2019．

  73. 小林靖明: 頂点Kaylesに対するモジュラ幅FPTアルゴリズム，組合せゲーム・パズルプロジェクト，第14回研究集会，東京，2019．

  74. 久保田稜，小林靖明，山本章博: 定数次数の木に対する高速な最適アラインメント計算について．人工知能学会 第108回人工知能基本問題研究会，大阪，2019．

  75. 小林靖明: 半順序集合の次元を求める固定パラメータアルゴリズム．基盤(S)離散構造処理系プロジェクト「2018年度 秋のワークショップ」，北海道，2018．

  76. 紫藤佑介，小林靖明，山本章博，宮本篤志，松村忠幸，嶺竜治: Tree-LSTMの拡張による抽象構文木のより良い分散表現獲得に向けて．第21回情報論的学習理論ワークショップ，北海道，2018.

  77. 小林 靖明: 構造的パラメータを用いた頂点Kaylesの解析．電子情報通信学会 コンピュテーション研究会，福岡，2018．

  78. 向井達郎，小林靖明，紫藤佑介，山本章博，宮本篤志，松村忠幸，嶺竜治: トークンのN-gramによるプログラム表現を用いたコードクローン検出手法 ．情報処理学会研究報告．第199回ソフトウェア工学研究発表会，2018，北海道．2019年度情報処理学会CS領域奨励賞 (向井君) (link)

  79. 小林靖明，玉置卓，宮崎修一: 少ない辺交差数を持つグラフにおける最大カット問題．基盤(S) 離散構造処理系プロジェクト 「2018年度 初夏のワークショップ」，北海道，2018．

  80. 久保田稜，小林靖明，山本章博: 整数計画法による木構造データ間のアラインメント距離の計算．人工知能学会 第106回人工知能基本問題研究会，鹿児島，2018．

  81. Yasuaki Kobayashi: On the size of concept lattices. 情報処理学会研究報告，第166回アルゴリズム研究会，沖縄，2018．

  82. 小林靖明，玉木久夫: 最小フィルイン問題に対する安全なセパレータ．情報処理学会研究報告，第164回アルゴリズム研究会，京都，2017．

  83. 紫藤佑介，山本章博，小林靖明，久保山哲二: モジュラリティを基準とした関係データに対する特徴選択．人工知能学会 第103回人工知能基本問題研究会，大分，2017．

  84. Hong Eunpyeong，小林靖明，山本章博: 整数計画法による木間距離の計算を高速化するための新しい定式化．人工知能学会 第103回人工知能基本問題研究会，大分，2017．

  85. 山浦智佳子，小林靖明，山本章博，久保山哲二: クラスタ構造を仮定した場合の双クラスタリングアルゴリズムの解析．人工知能学会 第103回人工知能基本問題研究会，大分，2017．

  86. 末續鴻輝，小林靖明，立木秀樹，山田修司: Parallel Crosses Puzzleとその計算量．第12回組合せゲーム・パズル プロジェクト研究集会，愛知，2017．

  87. 大塚広夢，小林靖明，玉木久夫: 交差数の少ない単一ページ描画における固定パラメータアルゴリズム．情報処理学会研究報告，第161回アルゴリズム研究会，岩手，2017．

  88. Hong Eunpyeong，小林靖明，山本章博: IP Solverを用いた木間距離の高速計算の改良．基盤(S) 離散構造処理系プロジェクト 「2016年度 秋のワークショップ」，北海道，2016．

  89. 小林靖明，玉木久夫: 頂点被覆数の小さいグラフに対するtreedepthの計算について．2016年夏のLAシンポジウム，奈良，2016.

  90. 小林靖明: グラフのカット幅を求める高速な厳密アルゴリズムの開発．学習院大学計算機センター特別研究プロジェクト成果報告会，東京，2016.

  91. 小林靖明，玉木久夫: 頂点被覆数の小さいグラフの最適消去木の計算について． 情報処理学会研究報告，第155回アルゴリズム研究会，鹿児島，2015.

  92. 橘内謙太，小林靖明，玉木久夫: 準完全有向グラフとその一般化に対するパス幅計算について． 情報処理学会研究報告，第152回アルゴリズム研究会，東京，2015.

  93. Yasuaki Kobayashi, Hisao Tamaki: Improved fixed parameter algorithm for two-layer crossing minimization．情報処理学会研究報告，第151回アルゴリズム研究会，愛知，2015.

  94. Yasuaki Kobayashi: Computing the pathwidth of directed graphs with small vertex cover. 情報処理学会研究報告，第148回アルゴリズム研究会，愛媛，2014．

  95. 小林靖明，小室慶太，玉木久夫: パス幅計算におけるコミットメントによる探索状態数削減: 実験的研究．情報処理学会研究報告，第148回アルゴリズム研究会，愛媛，2014．

  96. Yasuaki Kobayashi，Hirokazu Maruta，Yusuke Nakae，Hisao Tamaki: A linear edge kernel for two-layer crossing minimization．情報処理学会研究報告，第144回アルゴリズム研究会，北海道，2013． 情報処理学会コンピュータサイエンス領域奨励賞 (link)

  97. 小林靖明，玉木久夫: One-sided crossing minimizationに対する準指数時間固定パラメータアルゴリズム．日本オペレーションズ・リサーチ学会 「OR横断若手の会研究部会」，KSMAP琵琶湖合宿，2012． 学生優秀発表賞 (link)

  98. Yasuaki Kobayashi, Hisao Tamaki: A fast and simple subexponential fixed parameter algorithm for one-sided crossing minimization．情報処理学会研究報告，第141回アルゴリズム研究会，北海道，2012．

  99. Kenta Kitsunai, Yasuaki Kobayashi, Keita Komuro, Hisao Tamaki, Toshihiro Tano: Computing directed pathwidth in \(O(1.89^n)\) time．情報処理学会研究報告，第141回アルゴリズム研究会，北海道，2012．

  100. Yasuaki Kobayashi, Yuichiro Miyamoto, Hisao Tamaki: \(k\)-cyclic orientations of graphs. 情報処理学会研究報告，第134回アルゴリズム研究会，沖縄, 2011．

その他

  • 組合せゲームにおけるアルゴリズムと計算量．オペレーションズ・リサーチ 68巻3号，2023.

  • 多様な組合せを求めるアルゴリズム論的アプローチ．システム／制御／情報 66巻11号，2022.

  • 「密」を避ける．人工知能 36巻3号， 2021.

  • PACE Challenge への招待．LA会誌74号，2020.