山中寿登さんのスケジューリング学会奨励賞の受賞

山中寿登さん(M2)のスケジューリング学会奨励賞の授賞式がスケジューリングシンポジウム2018で行われました.受賞は,昨年のスケジューリングシンポジウムでの発表「外平面グラフに対するKollerのL(2,1)-ラベリングアルゴリズムの計算時間解析とその改善」に対するものです.

この研究は,Kollerによって提案されていた外平面グラフに対するL(2,1)-ラベリングを行う多項式時間アルゴリズムの計算量解析を精緻化した上で,さらにいくつかの高速化アイデアを組み込むことにより,Kollerの解析による計算量O(n^1001)をO(n^16.5)程度にまで改善したというものです.

山中さん,おめでとうございます.

Leave a Reply

Your email address will not be published. Required fields are marked *