自己紹介
東京大学の特任助教です。 理論計算機科学、とくに NP 困難問題に対するアルゴリズムの設計と解析を研究しています。 現在は、指数時間アルゴリズムを高速化するための代数的手法、パラメータ化・厳密アルゴリズム、グラフとマトロイドのアルゴリズム、数え上げ問題、脱乱択化、時間と空間のトレードオフに関心があります。
学歴
ベルリン工科大学
博士（情報科学）
2020年2月 - 2024年1月
博士論文: New Parameterized Algorithms for Matching and Packing Problems.
指導教員: Prof. Rolf Niedermeier.
ベルリン工科大学
修士（情報科学）
2017年10月 - 2019年12月
修士論文: Algorithmic and Structural Aspects of Matrix Completion Problems.
指導教員: Prof. Rolf Niedermeier.
東京大学
学士（電子情報工学）
2013年4月 - 2017年3月
卒業論文: An analytic approach for statistical properties of stochastic oscillators and its application.
指導教員: 長谷川 禎彦 准教授.
主な論文
完全な論文リストは DBLP または Google Scholar をご覧ください。
Determinantal Sieving
Eduard Eiben, Tomohiro Koana, Magnus Wahlström.
TheoretiCS 2025 |
SODA 2024
線形マトロイド上のパラメータ化アルゴリズムに対する代数的枠組み determinantal sieving を導入しました。多重線形項検出をマトロイド制約へ拡張し、複数の既存結果を高速化または簡潔化しています。
Faster Edge Coloring by Partition Sieving
Shyan Akmal, Tomohiro Koana.
STACS 2025
辺彩色問題に対し、標準的な 2^m 時間の枠組みを改善しつつ、多項式空間で動作する厳密アルゴリズムを与えました。古典的な NP 困難問題に対する高速な指数時間アルゴリズムへの一歩です。
Induced Matching Below Guarantees: Average Paves the Way for Fixed-Parameter Tractability
Tomohiro Koana.
STACS 2023
誘導マッチング問題の下限保証パラメータ化を研究しました。二つの自然な保証値は単独では固定パラメータ可解性を導きにくい一方、それらの平均を用いることで Gallai-Edmonds 分解に基づく FPT 分岐アルゴリズムを構築しています。
The Complexity of Finding Fair Many-To-One Matchings
Niclas Boehmer, Tomohiro Koana.
ACM Transactions on Algorithms 2024 |
ICALP 2022
属性を色で表す二部グラフ上の公平な多対一マッチングを解析しました。強い制約下での NP 困難性、構造パラメータに関する FPT アルゴリズム、Hall 型条件に基づく整数線形計画定式化を与えています。
Exploiting c-Closure in Kernelization Algorithms for Graph Problems
Tomohiro Koana, Christian Komusiewicz, Frank Sommer.
SIAM Journal on Discrete Mathematics 2022 |
ESA 2020
c-closed グラフモデルを古典的なグラフ問題のカーネル化に応用しました。c-closed グラフにおける Ramsey 型の多項式上界を鍵として、支配集合問題や誘導マッチング問題などに対する固定パラメータアルゴリズムと多項式カーネルを示しています。