グラフのパス被覆問題とマッチング問題の計算量を扱う．アルゴリズムでは順序アルゴリズムと、並列アルゴリズムを対象とする．
特に、サイクルを含まないグラフに対するこの問題に対する線形時間順序アルゴリズムとＮＣと言われるクラスに属する並列アルゴリズムの存在範囲をほぼ明らかにした．
研究者
修士課程（東京電機大学） 山神
訪問研究者 植村