情報処理学会 第79回全国大会講演要旨

グラフの頂点への非負整数の割り当てをラベリングという。本研究では距離2以下の頂点同士のラベル値に制約があるL(2,1)ラベリング問題（使用ラベル値範囲の最小化）を扱う。この問題は直並列グラフに限定してもNP困難であるが，木グラフに対しては線形時間アルゴリズムが知られている。本研究では，これらの中間に位置するグラフクラスである外平面グラフに対するKollerのアルゴリズム(2005)の計算量について考察する。Kollerによるとその計算量はO(n^{1001})であり，多項式時間ではあるものの非現実的である．本研究では, Kollerのアルゴリズムを整理，再構築し，精緻な計算量解析を行うことによりその計算時間をO(n^{26})程度まで削減する．